BZOJ 5085: 最大 – [二分/暴力]


题目传送门(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 
#include 
#include 
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();
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注