NC24622 Brownie Slicing

题目描述

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 making 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

示例1

输入

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

思路

知识点：二分，前缀和。

显然二分所有块的最小值。对于某个答案，只要让分的每块都的大于等于他即可。检查过程如下：

1. 因为行列划分不交叉，因此可以考虑先从行起始点 \(prea\) 开始划一个横条，对这一整条进行列划分出每一块。
2. 对于每一块，从列起始点 \(preb\) 记录其和 \(sum\)，到某一列 \(j\) 时到达答案就停止纳入，将列起始点 \(preb\) 更新到 \(j+1\) ，进行对下一块归纳，并且此横条的可划分块数 \(cntb\) 加一；否则继续纳入这个条的下一列。
3. 如果划分到某一行 \(i\) ，这一整条的 \(cntb >= B\) ，则说明这个横条划分合格，将把 \(prea\) 更新为 \(i+1\) ，并把矩阵可划分条数 \(cnta\) 加一;否则不合格，继续纳入下一行。
4. 最后如果 \(cnta >= A\) 说明行列划分合格，这答案是可行的；否则不合格。

注意到每次计算一个块的总和是重复的，考虑预处理二位前缀和，能直接计算出这块的大小为：

\[sum = N[i][j] - N[prea-1][j] - N[i][preb-1] + N[prea-1][preb-1]
\]

要注意的是，起始行列都是 \(1\) 不是 \(0\) 注意不要坑到自己qwq。

时间复杂度 \(O(RC)\)

空间复杂度 \(O(RC)\)

代码

#include <bits/stdc++.h>

using namespace std;

int R, C, A, B;
int N[507][507];

bool check(int mid) {
    int prea = 1, cnta = 0;///注意下标啊，起始行列都是1不是0
    for (int i = 1;i <= R;i++) {
        int preb = 1, cntb = 0;
        for (int j = 1;j <= C;j++) {
            int sum = N[i][j] - N[prea - 1][j] - N[i][preb - 1] + N[prea - 1][preb - 1];
            if (sum >= mid) {
                preb = j + 1;
                cntb++;
            }
        }
        if (cntb >= B) {
            prea = i + 1;
            cnta++;
        }
    }
    return cnta >= A;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> R >> C >> A >> B;
    for (int i = 1;i <= R;i++)
        for (int j = 1;j <= C;j++)
            cin >> N[i][j], N[i][j] += N[i - 1][j] + N[i][j - 1] - N[i - 1][j - 1];
    int l = 0, r = 1e9;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout << r << '\n';
    return 0;
}