TOJ 3453 Brownie Slicing / 二分
Brownie Slicing时间限制(普通/Java):2000MS/6000MS 运行内存限制:65536KByte
描述
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 N_ij (0 <= N_ij <= 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 易做图 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:
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1
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: N_i1, ..., N_iC
输出
* Line 1: A single integer: the maximum number of chocolate chips that Bessie guarantee on her brownie
样例输入
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
题意简单 把n*m的矩阵分成a*b块 使最小的矩阵和最大
二分出可能的值
对于每个 min 去判断是否可行
用贪心去判断 首先numa = 0
首先 i = j = 1 表明当前选择第j 到 i 行（j >= i）
然后去判断这几行是否能分成B块 如果大于等于B那么numa++;j++,i = j 不行的话就j++
最后numa >= A 就说明mid成立
#include <stdio.h>
const int MAX = 510;
int n,m,A,B;
int a[MAX][MAX];
int map[MAX][MAX];
bool check(int mid)
{
int numa = 0,numb = 0,sum;
int i = 1,j = 1,k;
while(j <= n)
{
numb = 0;
sum = 0;
for(k = 1; k <= m; k++)
{
sum += map[j][k] - map[i-1][k];
if(sum >= mid)
{
numb ++;
sum = 0;
}
}
if(numb >= B)
{
i = j+1;
j++;
numa++;
}
else
j++;
}
if(numa >= A)
return true;
return false;
}
int main()
{
int i,j,sum,l,r,mid;
scanf("%d %d %d %d",&n,&m,&A,&B);
{
r = 0;
sum = 0;
for(i = 1; i <= n; i++)
{
for(j = 1;j <= m; j++)
{
scanf("%d",&a[i][j]);
map[i][j] += map[i-1][j] + a[i][j];
sum += a[i][j];
}
}
l = 0;
r = sum / (A*B);
while(l <= r)
{
mid = (l + r) >> 1;
if(check(mid))
l = mid + 1;
else
r = mid - 1;
}
printf("%d\n",r);
}
return 0;
}
补充：软件开发 , C++ ,
