NSOqwq

题解 P3017 [USACO11MAR] Brownie Slicing G

题解 P3017 [USACO11MAR] Brownie Slicing G


Part 1 题目大意

有一块可以被看作一个 $R \times C$ 大小的方格的蛋糕,第 $i$ 行第 $j$ 列的方格上有 $N_{i,j}$ 块巧克力碎屑。首先要水平方向切 $A-1$ 刀,把蛋糕分成 $A$ 条;接着,对于每一条,竖直切 $B - 1$ 刀,分成 $B$ 块(注意,每一条蛋糕分割成 $B$ 小块的方式不必相同)。求问,巧克力碎屑最少的那块蛋糕最多有多少块巧克力碎屑。


Part 2 题目分析

这道题求的是最少的最多,而二分答案通常可以解决此类问题,由此想到二分答案的做法。

二分答案的一个重要特点:

问题可以被看作求使某个命题 $P(x)$ 成立(或不成立)的最大(或最小)的 $x$。

这道题显然满足这个特点,但是这个 $P(x)$ 是什么呢?可以转化一下,即,如果每一小块上的巧克力碎屑都至少为 $x$,是否能够将这块大蛋糕分成 $A$ 行 $B$ 列

接下来,我们来看一下是否满足单调性,当然对于此题显然是满足的。


最后一个问题,就是如何高效判断对于一个 $x$,$P(x)$ 是否成立。

由于「将每一条分成 $B$ 小块」这一部分的分割比较随意,于是很容易想到一种朴素做法:

对于每一行,检查是否能被切成每块巧克力碎屑数都至少为 $x$ 的 $B$ 小块,如果不行,则加入下一行,继续检查,直到可行为止,算作切好了一条。当所有行都被检查完,如果还不够切成 $A$ 条,则这个 $x$ 不可行。

这个做法有一个缺陷:当连续很多行都无法切成一条的时候,每新加入一行检查就需要重新算一遍之前几行,效率很低,于是自然地想到了二维前缀和优化。二维前缀和可以把时间复杂度降到 $O(R \times C)$ 以内。


Part 3 代码实现

#include <cstdio>
#define max(a, b) ( (a) > (b) ? (a) : (b) )
#define min(a, b) ( (a) < (b) ? (a) : (b) )
int r, c, a, b;
int pre[501][501];
inline int read() {
    int t = 0; bool neg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') neg = 1; ch = getchar(); }
    do { t = t * 10 + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
    if (neg) t = -t;
    return t;
}
int getSum(int x1, int y1, int x2, int y2) {
    return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}
bool check(int x) {
    int currA = 0, startR = 1;
    for (int i = 1; i <= r; ++i) {
        int currB = 0, startC = 1;
        for (int j = 1; j <= c; ++j) {
            if (getSum(startR, startC, i, j) >= x) {
                ++currB;
                startC = j + 1;
            }
        }
        if (currB >= b) {
            startR = i + 1;
            ++currA;
        }
    }
    return currA >= a;
}
int main() {
    r = read(), c = read(), a = read(), b = read();
    int lower = 1e8, upper = 0;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j) {
            int n = read();
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + n;
            upper += n;
            lower = min(lower, n);
        }
    int ans = 0;
    while (lower <= upper) { // 注意二分答案写法,这里我是按照《深基》上的写法写的。
        int mid = (lower + upper) >> 1;
        if (check(mid))
            ans = mid, lower = mid + 1;
        else
            upper = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}

2021-07-17 22:53:59 in 题解