Usaco*Brownie Slicing，usacobrownie
Description
Bessie烘焙了一塊巧克力蛋糕。這塊蛋糕是由R*C(1 <= R,C <= 500)個小的巧克力蛋糕組成的。 第i行，第j列的蛋糕有N_ij(1 <= N_ij <= 4,000)塊巧克力碎屑。 Bessie想把蛋糕分成A*B塊，(1 <= A <= R,1 <= B <= C): 給A*B只奶牛。蛋糕先水平地切A-1刀 （只能切沿整數坐標切）來把蛋糕劃分成A塊。然後再把剩下來的每一塊獨立地切B-1刀， 也只能切沿整數坐標切。其他A*B-1只奶牛就每人選一塊，留下一塊給Bessie。由於貪心， 他們只會留給Bessie巧克力碎屑最少的那塊。 求出Bessie最優情況下會獲得多少巧克力碎屑。 例如，考慮一個5*4的蛋糕，上面的碎屑分布如下圖所示： 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 Bessie必須把蛋糕切成4條，每條分成2塊。Bessie能像這樣切蛋糕: 1 2 | 2 1 --------- 3 | 1 1 1 --------- 2 0 1 | 3 --------- 1 1 | 1 1 1 1 | 1 1 因此，其他貪得無厭的牛拿完後，Bessie仍能夠拿走3個巧克力碎屑。
Input
* 第1行: 四個空格隔開的數: R, C, A ，B * 第2-R+1行: 第i+1行有C個整數, N_i1 , N_i2 .. N_iC
Output
* 第1行: 一個整數: Bessie保證能拿到的最多碎屑數
Sample Input
5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1
Sample Output
3
二分答案，貪心判斷以現在的值為答案能否切成a*b塊。
1 #include<cstdio>
2 #include<iostream>
3 using namespace std;
4 int a[501][501]={0};
5 int r,c,a1,b1;
6
7 bool check(int now)//判斷當前答案的正確性
8 {
9 int tot=0,x=0,y=0,j=0,i=0,lasti=0;
10 while (i<r)//i為訪問到第幾行，避免越界
11 {
12 ++i;
13 j=0;
14 y=0;//當前（lasti~i這一塊面包被豎著切成y塊面包）
15 while ((j<c)&&(y<b1))
16 {
17 tot=0;
18 while ((tot<now)&&(j<c))//利用貪心，一列一列加
19 {
20 ++j;
21 for (int i2=lasti+1;i2<=i;++i2)
22 tot=tot+a[i2][j];
23 }
24 if (tot>=now)//如果可以產生一塊新的面包，則將y+1
25 ++y;
26 }
27 if (y>=b1)//當lasti~i行的面包能被切成大於等於B（b1）塊且每一塊的碎屑都大於mid，x+1，開始枚舉下一次該切在哪
28 {
29 ++x;
30 lasti=i;
31 }
32 }34 if (x>=a1)
35 return true;
36 return false;
37 }
38
39 int main()
40 {
41 cin>>r>>c>>a1>>b1;
42 int right=0;
43 for (int i=1;i<=r;++i)
44 for (int j=1;j<=c;++j)
45 {
46 cin>>a[i][j];
47 right+=a[i][j];
48 }
49 int ans=0,left=0,mid=0;
50 while (left<=right)//二分答案
51 {
52 mid=(left+right)/2;
53 if (check(mid)==true)
54 {
55 left=mid+1;
56 ans=mid;//避免出現死循環
57 }
58 else right=mid-1;
59 }
60 cout<<ans<<endl;
61 return 0;
62 }
