房顶漏水啦【算法赛】

2023-12-23 22:38:54

问题描述

小蓝家的房顶是一个边长为?n?的正方形,可以看成是由?n×n?个边长为?1?的小正方形格子组成。

从上到下第?i?行、从左到右第?j?列的格子用?(i,j)?表示。

小蓝的家由于年久失修,导致房顶有一些地方漏水。总共有?m?处漏水的地方,我们用(x1?,y1?),(x2?,y2?)...(xm?,ym?)?来表示。

于是小蓝来到了五金店,五金店贩卖着一些正方形木板,木板的种类有?n?种,第?i?种木板的边长为?i。小蓝需要一块能够覆盖所有漏洞的木板,请问小蓝需要购买木板的最小边长是多少?

输入格式

第一行输入两个整数 n,m。

接下面?m?行,每行两个整数 (xi?,yi?)?代表第?i?个漏洞的位置。

输出格式

输出一个整数,代表木板的最小边长。

样例输入

5 3
3 3
5 3
4 4

样例输出

3

说明

房顶漏洞如下图所示,使用?3×3的正方形可以覆盖掉所有的漏洞。

样例

评测数据范围

运行限制

语言最大运行时间最大运行内存
C++1s256M
C1s256M
Java2s256M
Python33s512M
PyPy33s512M
Go3s512M
JavaScript3s512M

总通过次数: 903??|??总提交次数: 1518??|??通过率: 59.5%

难度: 中等???标签: 思维

解题思路

请在此处填写你的解题思路

一定要看清楚给的数字范围,要用long long int 然后用min1,min2和max1,max2分别记录行和列的最大和最小值,再相减加一,取max1-min1+1和max2-min2+1这两个中的最大值

#include <iostream>
using namespace std;
long long  int n,m,flag=0;
long long int bian=0,min1=0,max1=0,min2=0,max2=0;
int main()
{
  // 请在此输入您的代码
  cin>>n>>m;
  for(int i=0;i<m;i++){
     long long  int a,b;
    cin>>a>>b;
      if(flag==0){
          flag=1;
          min1=a,max1=a,min2=b,max2=b;
      }
      else{
          if(a<min1)
              min1=a;
          if(b<min2)
              min2=b;
          if(a>max1)
              max1=a;
          if(b>max2)
              max2=b;
      }
  }
    bian =max1-min1+1;
    if(bian<(max2-min2+1))
        bian=max2-min2+1;
  cout<<bian;
  return 0;
}

文章来源:https://blog.csdn.net/qq_73062949/article/details/135174841
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。