[10.08模拟赛] 建房 (二分)

[模拟赛] 建房

题目描述

ufo有一片矩形的土地。
ufo认为：这片土地可以视为一个n*m的矩阵，他打算在土地上盖房子，房子的价值等于所占土地的4个角上的数的最小值。
ufo对房子有一些简单的小要求：
1、房子是矩形的，且四条边必须平行于土地的边界。
2、房子的长和宽均不得小于2。
ufo想让你算一算：他的房子最大价值是多少。

输入

第一行2个整数n，m。
接下来n行，m列，描述ufo的土地。

输出

一行，一个整数表示ufo房子的最大价值。

样例输入

3 3
1 2 3
4 5 6
7 8 9

样例输出

提示

对于30%的数据 n<=100，m<=100，0<=矩阵中的数<=10000
对于另外20%的数据 0<=矩阵中的数<=1
对于100%的数据 n<=1000，m<=1000，0<=矩阵中的数<=10000000000

Solution

30分:模拟即可
50分:在30分的前提下,扫描矩阵中的1,对于第i行,若第j,k列都是1,则标记vis[j][k]=1,如果一个数组被标记了两次,则输出1
100分:二分,扫描矩阵,大于mid的记为1,否则记为0,然后结合50分的判定,可以AC

 for(lol i=1,top=0;i<=n;i++) {
        for(lol j=1;j<=m;j++)
            if(v[i][j]>=mid) s[++top]=j;
        for(lol j=1;j<top;j++) {
            for(lol k=j+1;k<=top;k++) {
                if(t[s[j]][s[k]]) return 1;
                t[s[j]][s[k]]=1;
            }
        }
    }return 0;

这个验证看似是(O(n^3))的,但是由于状态只有(n^2)个,所以在扫到(n^2)个后一定会(return)

Code

#include<bits/stdc++.h>
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
#define in(i) (i=read())
using namespace std;
const lol N=1010,inf=2e9;
lol read() {
    lol ans=0,f=1; char i=getchar();
    while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
    while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0',i=getchar();
    return ans*f;
}
lol n,m,ans,v[N][N],t[N][N],maxn,s[N];

lol check(lol mid) {
    memset(t,0,sizeof(t));
    for(lol i=1,top=0;i<=n;i++) {
        for(lol j=1;j<=m;j++)
            if(v[i][j]>=mid) s[++top]=j;
        for(lol j=1;j<top;j++) {
            for(lol k=j+1;k<=top;k++) {
                if(t[s[j]][s[k]]) return 1;
                t[s[j]][s[k]]=1;
            }
        }
    }return 0;
}

int main()
{
    //freopen("build.in","r",stdin);
    //freopen("build.out","w",stdout);
    lol c=0; in(n),in(m);
    if(n<2 || m<2) cout<<"0"<<endl,exit(0);
    for(rg lol i=1;i<=n;i++)
        for(rg lol j=1;j<=m;j++)
            in(v[i][j]),maxn=max(maxn,v[i][j]);
    lol l=0,r=maxn;
    while(l<r) {
        lol mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }cout<<l<<endl;
}