论水题与难题的差距：在于一个upper_bound
那么，这题一看就很显然了：因为答案满足二分性质所以我们二分。
然后我们再建造一个二维前缀和，每次判断的时候怎么办呢？
我先以为是贪心：选择以每个点为角落的正方形。后来瞬间构*例：
—————
丨 · 丨
丨 · 丨
丨· 丨
丨 · 丨
—————
然后考虑枚举：500 * 500， 随便水！
然后狂T不止...
发现在枚举内部我还有枚举，具体来说时间复杂度是：log10000 * 500 * 500 * 500
然后我改用了upper_bound，时间复杂度变为：log10000 * 500 * 500 * log500
然后果然A了！
/// poj3179
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = ; int a[N], b[N], x[N], y[N], g[N][N], sum[N][N], n, C, tx, ty; inline bool check(int k) {
//printf("check:%d\n", k);
int ans = ;
for(int i = ; i <= tx; i++) {
for(int j = ; j <= ty; j++) {
int ii = upper_bound(x + i, x + tx + , x[i] + k) - x - ;
int jj = upper_bound(y + j, y + ty + , y[j] + k) - y - ;
/// 就是这里！
//printf("%d %d %d %d ", i, j, ii, jj);
ans = max(ans, sum[ii][jj] - sum[ii][j - ] - sum[i - ][jj] + sum[i - ][j - ]);
if(ans >= C) return ;
//printf("ans=%d\n", ans);
//ii = i; jj = j;
//while(ii >= 0 && x[ii] - x[i] )
}
}
//printf("%d\n", ans);
return ans >= C;
} int main() {
int m = -;
scanf("%d%d", &C, &n);
for(int i = ; i <= n; i++) {
scanf("%d%d", &a[i], &b[i]);
x[i] = a[i];
y[i] = b[i];
m = max(m, x[i]);
m = max(m, y[i]);
}
sort(x + , x + n + );
sort(y + , y + n + );
for(int i = ; i <= n; i++) {
if(x[i] != x[i - ]) {
x[++tx] = x[i];
}
if(y[i] != y[i - ]) {
y[++ty] = y[i];
}
}
for(int i = ; i <= n; i++) {
int px = lower_bound(x + , x + tx + , a[i]) - x;
int py = lower_bound(y + , y + ty + , b[i]) - y;
g[px][py]++;
}
for(int i = ; i <= tx; i++) {
for(int j = ; j <= ty; j++) {
sum[i][j] = sum[i - ][j] + sum[i][j - ] - sum[i - ][j - ] + g[i][j];
}
}
int l = , r = m, mid;
while(l < r) {
mid = (l + r) >> ;
if(check(mid)) {
r = mid;
}
else l = mid + ;
}
printf("%d", r + );
return ;
}
AC代码
小细节：1 * 1的方框边长是0，n * n的方框边长是n - 1
所以我最后输出时 + 1