Brownie Slicing 【二分】

链接：https://ac.nowcoder.com/acm/contest/3886/B
来源：牛客网

题目描述

Bessie has baked a rectangular brownie that can be thought of as an RxC grid (1 <= R <= 500; 1 <= C <= 500) of little brownie squares. The square at row i, column j contains

NijN_{ij}Nij​ (0 <= NijN_{ij}Nij​ <= 4,000) chocolate chips. Bessie wants to partition the brownie up into A*B chunks (1 <= A <= R; 1 <= B <= C): one for each of the A*B cows. The brownie is cut by first making A-1 horizontal cuts (always along integer coordinates) to divide the brownie into A strips. Then cut each strip *independently* with B-1 vertical cuts, also on integer boundaries. The other A*B-1 cows then each choose a brownie piece, leaving the last chunk for Bessie. Being greedy, they leave Bessie the brownie that has the least number of chocolate chips on it. Determine the maximum number of chocolate chips Bessie can receive, assuming she cuts the brownies optimally. As an example, consider a 5 row x 4 column brownie with chips

distributed like this:

Bessie must partition the brownie into 4 horizontal strips, each with two pieces. Bessie can cut the brownie like this:

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

Thus, when the other greedy cows take their brownie piece, Bessie still gets 3 chocolate chips.

输入描述:

* Line 1: Four space-separated integers: R, C, A, and B
* Lines 2..R+1: Line i+1 contains C space-separated integers:  $Ni1,...,NiCN_{i1}, ..., N_{iC}Ni1​,...,NiC​$

输出描述:

* Line 1: A single integer: the maximum number of chocolate chips that Bessie guarantee on her brownie

示例1

输入

复制

输出

复制

3

思路
　　求一个最小值最大，很容易想到二分，枚举切行切列的情况 check
CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 507;
 47 
 48 int R,C,A,B;
 49 int a[maxn][maxn];
 50 int sum[maxn][maxn];
 51 
 52 bool check(int x) {
 53     int line_last, row_last;
 54     int line_have, row_have;
 55     line_have = 0, line_last = 0;
 56     
 57     for ( int i = 1; i <= R; ++i ) {
 58         row_have = 0, row_last = 0;
 59         for ( int j = 1; j <= C; ++j ) {
 60             //dbg(i), dbg(j);
 61             //printf("n1:%d n2:%d\n",sum[i][j] - sum[i][row_last] - sum[line_last][j] + sum[line_last][row_last],x);
 62             if(sum[i][j] - sum[i][row_last] - sum[line_last][j] + sum[line_last][row_last] >= x) {
 63                 row_have++;
 64                 row_last = j;
 65             }
 66         }
 67         if(row_have >= B) {
 68             line_last = i;
 69             line_have++;
 70         }
 71     }
 72     dbg(line_have);
 73     return line_have >= A;
 74 }
 75 
 76 int main()
 77 {
 78     int l = 1, r = 0, mid = 0;
 79     scanf("%d %d %d %d",&R, &C, &A, &B);
 80     for ( int i = 1; i <= R; ++i ) {
 81         for ( int j = 1; j <= C; ++j ) {
 82             scanf("%d",&a[i][j]);
 83         }
 84     }
 85     for ( int i = 1; i <= R; ++i ) {
 86         for ( int j = 1; j <= C; ++j ) {
 87             sum[i][j] = sum[i - 1][j] + sum[i][j-1] - sum[i - 1][j - 1] + a[i][j];
 88         }
 89     }
 90     
 91     l = 1;
 92     r = sum[R][C];
 93     while(l + 1 <  r) {
 94         mid = (l + r) >> 1;
 95         //printf("l:%d r:%d\n",l,r);
 96         //dbg(mid);
 97         if(check(mid)) {
 98             l = mid ;
 99         }
100         else {
101             r = mid ;
102         }
103     }
104     cout << l << endl;
105     return 0;
106 }

View Code