房顶漏水啦【算法赛】

问题描述

小蓝家的房顶是一个边长为?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++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	512M
PyPy3	3s	512M
Go	3s	512M
JavaScript	3s	512M

总通过次数: 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;
}