题解 P3017 【[USACO11MAR]布朗尼切片Brownie Slicing】

xMinh · 2017-10-31 13:02:47 · 题解

这道二分还真是不同于流俗啊

因为看错题，白白想了一个多小时。。。

好像没有c++的题解？

只要看懂题目的话其实还好

先二分最大化最小值

对于每一行，就像最基本的二分那样做，纵向切割

如果这一行不满足条件，就加上下一行继续判断

用now来保存上一个切点，用矩阵前缀和优化就行了

如果最后横向切割的次数大于等于a，就代表可以

PS:最后一行（列）也是要切一刀的

因为如果最后不能切的话就说明最后一段不满足条件

#include<iostream>
#include<cstdio>
using namespace std;
int r,c,a,b,map[501][501],s[501][501],ans;
bool check(int x)
{
    int now=0,num=0;
    for (int i=1;i<=r;i++)
    {
        int dis=0,sum=0;
        for (int j=1;j<=c;j++)
            if (dis+(s[i][j]-s[i][j-1])-(s[now][j]-s[now][j-1])<x)
                dis+=(s[i][j]-s[i][j-1])-(s[now][j]-s[now][j-1]);
            else
            {
                sum++;
                dis=0;
            }
        if (sum>=b)
        {
            now=i;num++;
        }
    }
    if (num<a) return 0;
    return 1; 
}
int main()
{
    cin>>r>>c>>a>>b;
    for (int i=1;i<=r;i++)
        for (int j=1;j<=c;j++)
            cin>>map[i][j];
    for (int i=1;i<=r;i++)
        for (int j=1;j<=c;j++)
            s[i][j]=s[i-1][j]+s[i][j-1]+map[i][j]-s[i-1][j-1];
    int h=0,t=s[r][c];
    while (h<=t)
    {
        int mid=(h+t)/2;
        if (check(mid))
        {
            h=mid+1;
            ans=mid;
        }
        else t=mid-1;
    }
    cout<<ans;
}