TP5 小田切蛋糕

思路： 先写好暴力解,通过分别枚举水平切和垂直切,选出所有符合要求的切法。为了快速判断是否符合要求,可以用前缀和。枚举时前缀和数组具有二分性,所以可以使用二分进行优化。 样例：

5 4 4 2 
1 2 2 1 
3 1 1 1 
2 0 1 3 
1 1 1 1 
1 1 1 1
3

解释： 如下图这样切：

1 2 | 2 1  
---------  
3 | 1 1 1  
---------  
2 0 1 | 3  
---------  
1 1 | 1 1  
1 1 | 1 1

这样，小田能获得 3 块巧克力碎屑。 代码：

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n[N][N],s[N][N];
int r,c,a,b;
int check(long long ans)
{
	int ni=1,cnt1=0;
	for(int i=1;i<=r;i++)
	{
		int nj=1,cnt2=0;
		for(int j=1;j<=c;j++)
		{
			int x=s[i][j]-s[ni-1][j]-s[i][nj-1]+s[ni-1][nj-1];
			if(x>=ans)
			{
				nj=j+1;
				cnt2++;
			}
		}
		if(cnt2>=b)
		{
			cnt1++;
			ni=i+1;
		}
	}
	return cnt1>=a;
}
int main()
{
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	cin>>r>>c>>a>>b;
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
		{	
			cin>>n[i][j];
			s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+n[i][j];
		}
	int l=0,rr=s[r][c],mid;
	while(l<rr)
	{
		mid=(l+rr+1)>>1;
		if(check(mid)) l=mid;
		else rr=mid-1;
	}
	cout<<l;
	return 0;
}

错误点： 1、return错了 2、二分写错