洛谷题单指南-前缀和差分与离散化-P3017 [USACO11MAR] Brownie Slicing G

原题链接：https://www.luogu.com.cn/problem/P3017

题意解读：将一个r*c的矩阵，横向切成a条，每一条纵向切除b块，计算每一块子矩阵之和的最小值最大是多少。

解题思路：

要计算最小值中最大的，直觉上可以采用二分，下面来分析单调性：

给定一个子矩阵块之和的值，值越小可以划分的条数、块数就越多，因此具备单调性。

因此，可以二分这个子矩阵块之和的最小值，然后检查是否可以划分成至少a条，每条至少b块，

如果可以，证明这个值还可以更大；如果不可以，证明这个值需要更小。最后得到的答案即最小值中最大的。

关键问题在于如何check，已知最小矩阵块之和x，计算是否能分成至少a条、每条至少b块？

只需要枚举每一行i、再对每一行枚举每一列j

记录新的一条的起始位置new_row，新的一列的起始位置new_col

利用前缀和，计算当前子矩阵的和s[i][j] - s[new_row - 1][j] - s[i][new_col - 1] + s[new_row - 1][new_col - 1]

只要子矩阵的和刚好大于等于x，证明可以在j处切一块，当前条的总块数累加，并更新下一块的起始位置

如果当前条总块数大于等于b，证明可以开始划分下一条，总条数累加，更新下一条的起始位置

如果总条数大于等于a，说明可以划分成功，返回true。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 505;

int w[N][N], s[N][N];
int r, c, a, b;

bool check(int x)
{
    int rows = 0, new_row = 1; //rows一共切了多少条，new_row新的一条从哪里开始
    for(int i = 1; i <= r; i++)
    {
        int cols = 0, new_col = 1; //cols当前条一共切了多少块，new_col新的一块从哪里开始
        int sum = 0; //当前块的和
        for(int j = 1; j <= c; j++)
        {
            int kuai = s[i][j] - s[new_row - 1][j] - s[i][new_col - 1] + s[new_row - 1][new_col - 1];
            if(kuai >= x) //贪心找到一个大于等于x的块
            {
                cols++; //当前条切一块
                new_col = j + 1; //更新新的一块开始位置
            }
        }
        if(cols >= b)
        {
            rows++;
            new_row = i + 1; //更新新的一条开始位置
        }
    }
    return rows >= a;
}

int main()
{
    cin >> r >> c >> a >> b;
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            cin >> w[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + w[i][j];
        }
    }

    int left = 0, right = s[r][c], ans = -1;
    while(left <= right)
    {
        int mid = left + right >> 1; //二分巧克力屑数最少的块的值
        if(check(mid)) 
        {
            ans = mid;
            left = mid + 1;
        }
        else right = mid - 1;
    }
    cout << ans;
    return 0;
}