P3017 [USACO11MAR]Brownie Slicing G 题解

Otomachi_Una_ · 2021-08-08 13:24:12 · 题解

题目简述

• 有一块 r\times c 的蛋糕，i 行 j 列上有 a_{ij} 的巧克力碎屑。
• 将其先沿水平方向切 a-1 刀，得到的 a 部分每部分都沿竖直方向切 b-1 刀。
• 在 a\times b 块切好的蛋糕中，巧克力碎屑的一块最少的一块最多有多少块巧克力碎屑？

解题思路

本题采用二分。

设 x 为等待检验的答案，last 为上一次横向切的位置，line 表示一共横向切了多少块。

显然，当 line>a 时，x 是可行的，反之亦然。

后使用两次贪心，每次发现可行的行就直接切，并更新 last,line。

对于如何判断是否可以直接切，只需看是否能把 last+1 到 i 行的蛋糕分成 b 块，每块的巧克力碎屑均不小于 x，这显然也是一次贪心。

参考代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=505;
int t[MAXN][MAXN];
int s[MAXN][MAXN];
int r,c,a,b;
int p,q,mid;
bool check(int x){
    int last=0,line=0;
    for(int i=1;i<=r;i++){
        int sum=0,ups=0;
        for(int j=1;j<=c;j++)
            if(s[i][j]-s[last][j]-s[i][ups]+s[last][ups]>=x)
                sum++,ups=j;
        if(sum>=b)
            line++,last=i;
    }
    return line>=a;
}
int main(){
    cin>>r>>c>>a>>b;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++){
            cin>>t[i][j];
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+t[i][j];
        }
    p=0,q=1e9;
    while(q>p){
        mid=(p+q+1)/2;
        if(check(mid)) p=mid;
        else q=mid-1;
    }
    cout<<p;
    return 0;
}