[JZOJ3918]蛋糕

description

今天是Bessie的生日,他买了一个蛋糕和朋友们一起分享,蛋糕可以看成是一个R行C列的表格,共有R*C个格子,每个格子都有一个0至9的数字,表示该格子蛋糕拥有的巧克力。现在Bessie要把蛋糕横的切3刀再竖的切3刀,由于Bessie刀法厉害,所以每个格子蛋糕都是完整的,显然蛋糕会被切成16份,然后Bessie和他的15个朋友们每人拿一份,Bessie比较客气,总是等其他朋友拿完了,Bessie拿最后剩下的那一份。Bessie的朋友们都很不客气,都是挑最多巧克力的那份去拿,于是Bessie最后拿到手的那份蛋糕总是巧克力总和最少的。Bessie心想:既然自己总是最后拿蛋糕,那应该怎么切蛋糕,才能使得自己拿的那部分蛋糕的有尽量多的巧克力呢?这个问题自然是你的任务了。


analysis
  • 要求最大值最小,先二分一个答案

  • 对于竖行, O ( n 3 ) O(n^3) O(n3)枚举切哪三列,然后剩下用三个二分找出可以满足条件的最小矩形

  • 如果十六个矩形的和的最小值都大于二分的答案则可以把答案取大,否则取小

  • 时间复杂度 O ( n 3 l o g 2 n ) O(n^3log^2n) O(n3log2n)


code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#includestdio.h
#includestring.h
#includealgorithm
#define MAXN 105
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i=b;++i)
#define fd(i,a,b) for (reg i=a;i=b;--i)

using namespace std;

ll a[MAXN][MAXN],sum[MAXN][MAXN];
ll n,m,num;

inline ll get(ll x,ll y,ll xx,ll yy){return sum[xx][yy]-sum[x-1][yy]-sum[xx][y-1]+sum[x-1][y-1];}
inline bool judge(ll x)
{
	fo(i,1,m-1)fo(j,i+1,m-1)fo(k,j+1,m-1)
	{
		ll l=1,r=n,mid,las;
		while (lr)mid=(l+r)1,min(min(get(1,1,mid,i),get(1,i+1,mid,j)),min(get(1,j+1,mid,k),get(1,k+1,mid,m)))=x?r=mid:l=mid+1;
		if (!r)continue;

		las=l=r+1,r=n;
		while (lr)mid=(l+r)1,min(min(get(las,1,mid,i),get(las,i+1,mid,j)),min(get(las,j+1,mid,k),get(las,k+1,mid,m)))=x?r=mid:l=mid+1;
		if (rlas)continue;

		las=l=r+1,r=n;
		while (lr)mid=(l+r)1,min(min(get(las,1,mid,i),get(las,i+1,mid,j)),min(get(las,j+1,mid,k),get(las,k+1,mid,m)))=x?r=mid:l=mid+1;
		if (rlas)continue;

		if (min(min(get(r+1,1,n,i),get(r+1,i+1,n,j)),min(get(r+1,j+1,n,k),get(r+1,k+1,n,m)))=x)return 1;
	}
	return 0;
}
int main()
{
	//freopen("T1.in","r",stdin);
	scanf("%lld%lld\n",n,m);
	fo(i,1,n){fo(j,1,m)num+=(a[i][j]=getchar()-'0');scanf("\n");}
	fo(i,1,n)fo(j,1,m)sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
	ll l=0,r=num/16,mid;
	while (l=r)mid=(l+r)1,judge(mid)?l=mid+1:r=mid-1;
	printf("%lld\n",r);
	return 0;
}
最新回复(0)
/jishux_2FgzTi6l8ubXmq_2FAT3FmufZKBGx9SST1hlR6noVg1tM_3D4858327
8 简首页