【AcWing】AcWing 5180. 正方形泳池（秋季每日一题2023）（排序 + 边枚举边更新）

题目

https://www.acwing.com/problem/content/5183/

题目大意，给定一个地图，给定若干颗树的坐标。要求不包含树的最大子正方形的边长。

思路

题目范围里，N有$10^5$，太大了，枚举肯定会超时，所以只能考虑枚举树。

最暴力的做法就是枚举4颗树，然后确定上边界、下边界、左边界、右边界，根据边界确定长和宽，最后求长、宽的最小值。这样的话复杂度是$C_{100}^4$，大概是$10^6$，是可以过的。

进一步分析，如果我们把树的坐标按照水平方向排序，即按y排序，每次从左到右依次枚举水平方向的两棵树。（我个人认为排序对于这一题来说还挺重要的，如果不排序的话，感觉一直陷在暴力枚举的思路里）当水平方向的两棵树确定之后，可以发现，垂直方向的树一定在之前枚举过的水平方向的树中选择。所以我们可以在枚举水平方向第二棵树的同时，用树的x坐标更新上下边界，这样再枚举下一个水平方向的第二棵树的时候，可以直接根据之前更新的上下边界确定竖直方向两个边界（这一点很重要，直接少枚举了两棵树）。

同样的，竖直方向也要枚举一遍。把每颗树的x、y坐标交换，然后按上述步骤重新做一遍。最后求两种情况下的最大值即可。

另外需要注意一下特殊情况，比如样例1，只有1颗树。这种情况可以把四个角落都人为的设置一棵树。

#include 
#include 

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII tr[N];

int work() {
    // 将树按横坐标排序
    sort(tr, tr + m);
    int res = 0;
    for(int i = 0; i < m; i ++ ) { // 枚举左边界 
        int up = n + 1, down = 0;
        for(int j = i + 1; j < m; j ++ ) { // 枚举右边界
            if (up - down < tr[j].x - tr[i].x) break; // 如果上下距离比左右还小，说明是被上下限制的，那后面就不用再枚举了。后面由于横向距离越来越大，一定都会被这个上下距离限制
            res = max(res, tr[j].x - tr[i].x - 1); // 更新答案
            
            // 边枚举，边更新上下边界
            // 因为当左右边界确定之后，剩下两个一定在这两个点之间。所以可以边枚举边更新上边界和下边界
            if (tr[j].y >= tr[i].y) up = min(up, tr[j].y);
            if (tr[j].y <= tr[i].y) down = max(down, tr[j].y);
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++ ) scanf("%d%d", &tr[i].x, &tr[i].y);
    
    // 加上4个角
    // 按道理来说，应该上下左右全部加上。但是由于
    tr[m ++ ] = {0, 0};
    tr[m ++ ] = {0, n + 1};
    tr[m ++ ] = {n + 1, 0};
    tr[m ++ ] = {n + 1, n + 1};
    
    int res = work();
    for(int i = 0; i < m; i ++ ) swap(tr[i].x, tr[i].y); // 把y和x交换一次，再做一遍，等价于枚举垂直方向
    printf("%d\n", max(res, work()));
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

总结

• 有时候排序可以帮助我们从暴力枚举的思路里解脱出来
• 边枚举边更新是一个很重要的思想