AcWing-121-赶牛入圈

问题

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

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含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

思路

离散化＋二分＋前缀和。将所有的坐标离散化，变为 1000*1000范围内的区域，求出该区域内的前缀和，再二分围栏长度，进行判断（遍历所有x轴长度小于等于len的线段，以及y轴长度小于等于len的线段，其围成的矩形必然包含于边长为len的正方形内部，判断该区域内的所有草坪的数量是否大于等于目标的c单位，满足则放回ture，否则返回false）。

题解

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

using namespace std;

typedef pair<int, int> PII;
const int MAX = 1010;

int n, c;
PII points[MAX];
vector<int> nums;
int sum[MAX][MAX];

//查找离散化后的下标
int get_index(int x) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (nums[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return l;
}

//此步骤注意草坪在坐标的右上方区域内
bool check(int len) {
    // x1代表在以x2结尾长度为len的区间前面的第一个点
    for (int x1 = 0, x2 = 1; x2 < nums.size(); x2++) {
        while (nums[x2] - nums[x1 + 1] + 1 > len) x1++;
        // y1代表在以y2结尾长度为len的区间前面的第一个点
        for (int y1 = 0, y2 = 1; y2 < nums.size(); y2++) {
            while (nums[y2] - nums[y1 + 1] + 1 > len) y1++;
            if (sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] >= c) return true;
        }
    }

    return false;
}

int main() {
    cin >> c >> n;
    nums.push_back(0);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        points[i] = {x, y};
        nums.push_back(x);
        nums.push_back(y);
    }

    //离散化
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());   //去除重复元素
    // unique将重复的元素放在最后，返回第一个不相同元素的迭代器
    //erase将两个迭代器之间的元素删除掉

    for (int i = 0; i < n; ++i) {
        int x = get_index(points[i].first), y = get_index(points[i].second);
        sum[x][y]++;
    }

    //求前缀和
    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 1; j < nums.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 << l << endl;

    return 0;
}