BZOJ 5085 最大

题目大意

给你一个$N \times M$的矩形，要你找一个子矩形，价值为左上角左下角右上角右下角这四个数的最小值，要你最大化矩形的价值。

神题啊……

考虑二分答案。对于一个答案我们可以把整个矩形转化成01矩阵，之后目的就是选出一个四个角都是1的矩阵。

之后就不会了……

求一个这样的矩阵其实就是求两条水平方向上的平行线段。实际上暴力就可以解决问题。

因为这样的线段最多只有$M^2$个，而且只要发生冲突出现两个就出解了……所以直接暴力的复杂度是正确的。

应用了从答案入手的反向思考的思想。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 1010

int n,m,v[N][N],pos[N][N],cnt[N],res[N*N*2],minn=0x3f3f3f3f,maxn=0xefefefef;

inline int RI()
{
	int ret=0,mus=1;char tmp=getchar();
	while(tmp<'0'||tmp>'9')
	{
		if(tmp=='-') mus=-1;
		tmp=getchar();
	}
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret*mus;
}

bool check(int tg)
{
	memset(cnt,0,sizeof cnt);
	memset(res,0,sizeof res);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			if(v[i][j]>=tg) pos[i][++cnt[i]]=j;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=cnt[i];++j)
			for(int k=1;k<=cnt[i];++k)
				if(j!=k)
				{
					if(res[pos[i][j]*n+pos[i][k]]) return true;
					res[pos[i][j]*n+pos[i][k]]++;
				}
	return false;
}

int bisection()
{
	int l=minn,r=maxn+1,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid)) l=mid+1;
		else r=mid;
	}
	return l-1;
}

int main()
{
	n=RI(),m=RI();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			v[i][j]=RI();
			minn=min(minn,v[i][j]),maxn=max(maxn,v[i][j]);
		}
	printf("%d\n",bisection());
	return 0;
}