题目描述

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含C单位的三叶草，来当做它们的下午茶。

畜栏的边缘必须与X，Y轴平行。

约翰的土地里一共包含N单位的三叶草，每单位三叶草位于一个1 x 1的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的X,Y坐标都为整数，范围在1到10000以内。

多个单位的三叶草可能会位于同一个1 x 1的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下，能包含至少C单位面积三叶草的情况下，畜栏的最小边长是多少。
输入格式

第一行输入两个整数 C 和 N。

接下来 N 行，每行输入两个整数 X 和 Y，代表三叶草所在的区域的X,Y坐标。

同一行数据用空格隔开。
输出格式

输出一个整数，代表畜栏的最小边长。

数据范围

1≤C≤500

C≤N≤500

样例

输入样例：

3 4
1 2
2 1
4 1
5 2

输出样例：

4

蒟蒻的我在yxc的思想指导下写的第一个题解

离散化 + 二维数组前缀和 + 二分查找

坐标的范围在1 ~ 10000，如果直接开二维数组遍历显然不现实，再看N的范围最大是500，那么我们就可以将坐标离散化后存在一个数组里，用这个数组来进行前缀和运算的操作，就会大大降低时间复杂度。

但要注意的是，这珠作死的草会在 1 × 1 的方格里，所以在算正方形边长的时候，需要在 x2 - x1 之后 再加上一个单位长度，y1,y2同理（x1,y1,x2,y2是当前选取的正方形的左上角和右下角的坐标）。而在算边长的时候，需要查找离散化之前的坐标来进行运算。最后需要提的是，这珠草可以正好落在正方形边长上，所以在最后计算一个正方形范围内的草的数目的时候公式应该为

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

不同于之前的激光炸弹，激光炸弹因为不能算边界，所以不需要-1。
剩下的，就请自己看代码吧。第一次写题解，写的不好请多原谅！！！
同时也请各位大佬指点！！！

C++ 代码

# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

typedef pair<int, int> PII;
int N, C;
int sum[1010][1010];   //前缀和  因为x跟y最多会有1000个不同的坐标，所以开大一点避免溢出
vector<PII> points;  //点的坐标
vector<int> numbers; //离散化结果

int get_id(int n)
{
    return lower_bound(numbers.begin(), numbers.end(), n) - numbers.begin();
}

bool check(int len)
{
    for (int x1 = 1, x2 = 1; x2 < numbers.size(); x2++) {
        while (numbers[x2] - numbers[x1] + 1 > len) x1++;
        for (int y1 = 1, y2 = 1; y2 < numbers.size(); y2++) {
            while (numbers[y2] - numbers[y1] + 1 > len) y1++;
            if (sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] >= C) return true;
            //因为包括边界，所以左上角坐标需要-1
        }
    }
    return false;
}

int main()
{
    cin >> C >> N;
    numbers.push_back(0);
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        numbers.push_back(x);
        numbers.push_back(y);
        points.push_back({ x, y });
    }
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
    //因为相同的数字只需要一个离散化的结果
    for (int i = 0; i < N; i++) {
        int x = get_id(points[i].first), y = get_id(points[i].second);
        sum[x][y]++;
    }
    for (int i = 1; i < numbers.size(); i++)
        for (int j = 1; j < numbers.size(); j++)
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    int l = 1, r = 10000;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}