題意：
給你一個蛋糕，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