stdKonjac's Blog

An AC a day keeps the WA away ~

【Cut】

【问题描述】

给你一块R*C的蛋糕,蛋糕上每一格都有巧克力,现在要横着切A-1刀然后对每个切下来的横条纵着切B-1刀,现在要求巧克力最少的那块蛋糕的巧克力数最多,求这个最多的巧克力数。

【输入格式】

第一行四个整数R C A B

接下来R行,每行C个数,描述每个格子上的巧克力数。

【输入样例】

5 4 4 2

1 2 21

3 1 1 1

2 0 1 3

1 1 1 1

1 1 1 1

【输出样例】

3

【样例说明】

1 2 | 2 1

————

3 | 1 1 1

————

2 0 1 | 3

————

1 1 | 1 1

1 1 | 1 1

最后一块那两个|是连在一起的,表示一刀。

【数据范围】

对100%的输入数据:1≤R,C≤500 1≤A≤R 1≤B≤C A[i][j]≤4000

求最小值最大这类题显然用二分来做,这道题我们可以二分最少的那块的巧克力数,然后为了尽可能切到A-1到,每一刀都尽可能再上面比较好,所以可以模拟切的过程,从小到大枚举当前刀切在哪一层,代入验证能不能切到B-1刀即可。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.