C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+6;
typedef pair<int,int> PII;

int n, c;
int sum[1010][1010]; //用来存前缀和
vector<PII> a;       //存坐标
vector<int> num;     //存离散化后的位置

bool check(int len)
{
    for(int x1 = 1, x2 = 1; x2 < num.size(); x2 ++)//将x的两个坐标开始枚举
    {
        while(num[x2]-num[x1]+1 > len) x1 ++;      //保证两个x距离刚好是len
        for(int y1 = 1, y2 = 1; y2 < num.size(); y2 ++) 
        {
            while(num[y2]-num[y1] +1 > len) y1 ++; //两个加一是因为艹的位置在方格内
            if(sum[x2][y2] - sum[x1-1][y2]-sum[x2][y1-1] + sum[x1-1][y1-1] >= c) //利用前缀和看是否艹够了
            return true; //如果够，则返回true
        }
    }
    return false;
}

int get(int x)
{
    return lower_bound(num.begin(),num.end(),x)-num.begin(); //利用二分返回x在离散化后的位置
}

int main()
{
    scanf("%d%d",&c,&n);
    num.push_back(0);
    for(int i = 0; i < n; i ++)
    {
        int x, y;
        scanf("%d%d",&x,&y);
        num.push_back(x);      //不分x，y 都先放入
        num.push_back(y);
        a.push_back({x,y});    //将位置记录下来
    }

    sort(num.begin(),num.end());                           //这两步是离散化
    num.erase(unique(num.begin(),num.end()),num.end());

    for(int i = 0; i < n; i ++)
    {
        int x = get(a[i].first);          //离散化后将刚刚存的所有坐标在离散化后的
        int y = get(a[i].second);         //数组里面找到相应的位置，然后该位置记录有一颗艹
        sum[x][y] ++;
    }

    for(int i = 0; i < num.size(); i ++)        //二维数组的前缀和
    {
        for(int j = 0; j < num.size(); j ++)
        {
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    }

    int l = 1; int r = 10000;
    while(l < r)                //用二分来枚举正方形的边长
    {
        int mid = l +r >> 1;
        if(check(mid)) r = mid; //如果这个边长内有大于等于c的艹
        else l = mid + 1;
    }

    cout << r << endl;
}