题目传送门(BZOJ)
>原文链接<

题解 :

最大化最小值, 明显的二分标志, 考虑二分答案

我们对于每行记录有哪些点是大于当前mid的, 然后对于每行$m^2$的枚举记录下来的点$(u, v)$,

开个桶, 令$Bukit[u][v] = 1$

相当于记录某个线段已经访问过, 如果下次再访问的话这个答案就合法了.

如果你认为验证复杂度是$O(nm^2)$的, 只能说明你太naive了, 发现最多有$m^2$条线段, 然而一旦某条线段出现两次, 就会直接return true了, 所以验证的上界应该是$n\times m+m^2$的

听说之前的数据puts("1000000000");可以AC ?

代码 :

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int a[1010][1010], n, m, l, r;int f[1010][1010], b[1010];bool check(int x) { memset(f, 0, sizeof f); for(int i = 1; i <= n; i ++ ) { *b = 0; for(int j = 1; j <= m; j ++ ) if(a[i][j] >= x) b[++*b] = j; for(int j = 1; j <= *b;j ++ ) for(int k = j+1; k <= *b; k ++ ) { if(f[b[j]][b[k]]) return 1; f[b[j]][b[k]] = 1; } } return 0;}int main() { scanf("%d%d", &n, &m); l = 1<<30; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) { scanf("%d", &a[i][j]); l = min(l, a[i][j]); r = max(r, a[i][j]); } int ans = 0; while(l <= r) { int mid = (l+r) >> 1; if(check(mid)) ans = mid, l = mid+1; else r = mid-1; } printf("%d\n", ans); getchar(), getchar();}