题目链接

算法竞赛进阶指南-34.赶牛入圈

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

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

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

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

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

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

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

输入格式

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

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

同一行数据用空格隔开。

输出格式

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

数据范围

$1 \le C \le 500$,
$C \le N \le 500$

输入样例：

3 4
1 2
2 1
4 1
5 2

输出样例：

4

Method : 离散化 + 前缀和 + 二分

首先这道题的意思，就是平面坐标系给你n个点，要求至少包含里面c个点的正方形，其边长最短是多少。(注意点是可以重合的，同一个坐标可以有多个点。)

这道题很容易看出来是二分答案，但由于是二维的，写起来像是二维版的袭击。

最关键的就是正方形的选取，是怎么枚举的？

最优的正方形，一定是至少两条对边都有点，否则可以缩小这个正方形的边长，直到这个正方形两条对边上有点。

根据这个特点我们可以枚举一个判断包含的check函数，再在外面套一层二分答案。

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

using namespace std;

typedef pair<int, int> PII;

const int N = 500 + 7;
const int M = N << 1;

vector<PII> points;
vector<int> numbers;
int sum[M][M];
int C, n;

int main() {
    memset(sum, 0, sizeof sum);
    
    cin >> C >> n;
    numbers.push_back(0); // 从0开始，方便前缀和计算
    int x_max = -1, y_max = -1;
    for (int i = 0;i < n; i ++) {
        int x, y;
        scanf("%d %d", &x, &y);
        x_max = max(x_max, x);
        y_max = max(y_max, y);
        
        points.push_back({x, y});
        numbers.push_back(x);
        numbers.push_back(y);
    }
    
    // 离散化
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
    
    for (int i = 0; i < n; i ++) {
        // 二分查找
        int x = lower_bound(numbers.begin(), numbers.end(), points[i].first) - numbers.begin();
        int y = lower_bound(numbers.begin(), numbers.end(), points[i].second) - numbers.begin();
        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];
        }
    }
    
    // 二分答案
    auto check = [&](int len) {
        // 枚举所有可能的正方形
        for (int x1 = 1, x2 = 1; x2 < numbers.size(); x2 ++){
            //  num[x1] + 1, 外面这个+1是实际的边长，因为每个单位是一个1 * 1的小方块
            while(x1 < x2 && numbers[x2] - numbers[x1] + 1 > len) x1 ++;
            for (int y1 = 1, y2 = 1; y2 < numbers.size(); y2 ++){
                while(y1 < y2 && numbers[y2] - numbers[y1] + 1 > len) y1 ++;
                // 要包含(x1, y1)这个边界点，因此x1 - 1, y1 - 1
                if (sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] >= C) {
                    return true; // 合法
                } 
            }
        }
        
        return false;
    };
    
    int l = 1, r = max(x_max, y_max);
    while (l != r + 1) {
        int mid = l + r >> 1;
        if (check(mid)) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    
    cout << r + 1 << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度${O(n\log n + n^2\log n)}$， 首先前面的离散化排序sort和2n次二分查找都是$O(n\log n)$的，然后二分答案的check是两重for循环, 里面的while循环几乎只执行1次(相邻)是$O(n^2)$，外面套一层二分答案$\log n$，因此是$O(n^2\log n)$。

• 空间复杂度${O((2n)^ 2)}$ 主要是$sum[M][M]$。

参考:

https://www.acwing.com/solution/content/1091/