题意：
给你一个蛋糕，R行C列 ，每个点有巧克力碎屑（如下）
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
你要先横着切a-1刀，将蛋糕分为a块，然后对于每一块，分别竖着切b-1刀
将整个蛋糕分成a*b块，求巧克力屑最少的一块最多有多少屑
思路：对于这种最大求最小，或者最小求最大的题目，我们往往会先往二分方面想
对于这道题，就是用二分的解法。
这道题让我们求最小值最大。
在计算的时候，我们先计算出二维前缀和。然后开始跑check
check部分，我们先计算只有一行的情况，如果不满足(（区间值>=mid的个数)>=B))，就继续增加行数，直到满足为止
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int inf=0x3f3f3f3f;
4 const int maxn=5e2+10;
5 int r,c,A,B;
6 int sum[maxn][maxn];
7 int a[maxn][maxn];
8 int cal(int x1,int y1,int x2,int y2){
9 int val=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
10 return val;
11 }
12 void init()
13 {
14 for(int i=1;i<=r;i++)
15 for(int j=1;j<=c;j++)
16 sum[i][j]=sum[i][j-1]+a[i][j];
17 for(int i=1;i<=r;i++)
18 for(int j=1;j<=c;j++)
19 sum[i][j]+=sum[i-1][j];
20 }
21 int check(int mid)
22 {
23 int nowL=1;int nowR=1;
24 int hang=0;
25 while(nowR<=r){
26 int tmp=1;int lie=0;
27 for(int i=1;i<=c;i++){
28 if(cal(nowL,tmp,nowR,i)>=mid){
29 lie++;
30 tmp=i+1;
31 }
32 }
33 if(lie<B) nowR++;
34 else{
35 hang++;
36 nowL=nowR+1;
37 nowR=nowL;
38 }
39 }
40 if(hang>=A) return 1;
41 else return 0;
42 }
43 int main()
44 {
45 scanf("%d%d%d%d",&r,&c,&A,&B);
46 for(int i=1;i<=r;i++){
47 for(int j=1;j<=c;j++){
48 scanf("%d",&a[i][j]);
49 }
50 }
51 init();
52 int L=0;int R=inf;
53 int ans;
54 while(L<=R){
55 int mid=L+R>>1;
56 if(check(mid)){
57 L=mid+1;
58 ans=mid;
59 }
60 else{
61 R=mid-1;
62 }
63 }
64 printf("%d\n",ans);
65 return 0;
66 } View Code