洛谷：P3017：Brownie Slicing

题目

P3017：Brownie Slicing

分析

直觉告诉我们：要保证最大最小值，一个必然可行的策略是所有人都拿到一样数量的巧克力！否则，一定会有一个最小数量成为切蛋糕的人获得的数量。在这个前提下，即使有人拿到更多，但我们保证我们拿到的最小数量可以最大化。

二分查找

一般而言，看到“最大-最小”问题，总有二分查找的用武之地。具体到本题，就是保证拿到的、最少的巧克力的那块蛋糕切片上的巧克力数量最大。二分查找的出发点在于：我们不知道这个最大最小值应该是多少，但一定有一个范围，比如说：从0到最大（所有巧克力数量之和）。

再来证明单调性。显然，如果对于某个数量（\(x_2\)）存在一种切割方案能满足我们的要求，那么这个方案对于任何数量要求（\(x_1 \lt x_2\)）一定也是可行的，而且可以试着尝试更贪心（拿到更多巧克力）的切法。而如果不存在一种切割方法，那么对于任何\(x_1\ge x_2\)，也一定没有可行的切法。

核心代码如下：

    int left = 0, right = prefix_sum[rows][cols];

    while (left <= right)
    {
        int mid = (left + right) / 2;

        if (can_guarantee_min_beans(mid))
        {
            left = mid + 1;
            max_guaranteed_beans = mid;  // 更新答案
        }
        else
        {
            right = mid - 1;
        }
    }

问题来到：如何判定对于某个数量，存在一种切法（can_gurantee_min_beans）。

计算某个数量是否可行

首先，这不是一个算平均值的过程。这里我们的算法有一些创意。尽管从某个角度看，这种后一个切法由前一个切法确定的过程有点DP的味道，但实际上不可行。我让Kiro试过用DP解决，但数据量大了之后，存在TLE问题。

核心的思路是：

1. 针对某一行，尝试从左到右尝试切分的边界。如果：切到某列的时候，从左到右这一条中的巧克力数量满足要求，那么纵向切条数+1，更新切分起始位置。
2. 对于这一行，继续这个工作：从切分位置开始找下一个切分位置。成功的话，就更新纵向切条数，更新切分起始位置。
3. 这一行是否切分成功，就是判断纵向切条数>=要求的纵向切条数。
4. 如果这一行不能切分成功，那么需要扩行。也就是从当前行切到下一行——也就是切两行。计算这两行从左到右是否可行。
5. 如果两行不行，试试三行、四行……如果成功了，那么更新起始切分行，同时横向切条数+1。
6. 最终是否成功，取决于最后的横向切条数是否大于等于要求的横向切条数。

bool can_guarantee_min_beans(int min_beans)
{
    int strip_start_row = 0;   // 当前条带的起始行
    int completed_strips = 0;  // 已完成的水平条带数量

    for (int current_row = 1; current_row <= rows; current_row++)
    {
        int piece_start_col = 1;   // 当前垂直块的起始列
        int pieces_in_strip = 0;   // 当前条带中的垂直块数量

        for (int col = 1; col <= cols; col++)
        {
            // 计算当前垂直块的巧克力豆总数 [strip_start_row+1, piece_start_col] 到 [current_row, col]
            int piece_beans = get_rectangle_sum(strip_start_row + 1, piece_start_col, 
                                              current_row, col);

            // 如果当前块已经满足最小要求，就切割形成一个垂直块
            if (piece_beans >= min_beans)
            {
                pieces_in_strip++;
                piece_start_col = col + 1;  // 下一个垂直块从下一列开始
            }
        }

        // 检查当前条带是否能分出足够的垂直块
        if (pieces_in_strip >= vertical_pieces)
        {
            strip_start_row = current_row;  // 当前条带成功，下一条带从下一行开始
            completed_strips++;
        }
    }

    // 检查是否完成了足够的水平条带
    return completed_strips >= horizontal_strips;
}

前缀和计算某个切条范围内的巧克力数量

构造前缀和的公式是一样的：¹

for (int i = 1; i <= rows; i++)
    for (int j = 1; j <= cols; j++)
        prefix_sum[i][j] = prefix_sum[i - 1][j] + prefix_sum[i][j - 1] +
                           grid[i][j] - prefix_sum[i - 1][j - 1];

某个切条范围由起始行（strip_start_row）、当前行（current_row）、起始列（strip_start_row）、当前列（col）决定。因此根据前缀和求该范围的和的公式就是：

prefix_sum[r2][c2] - prefix_sum[r1-1][c2] - prefix_sum[r2][c1-1] + prefix_sum[r1-1][c1-1];

注意，在调用的时候，int piece_beans = get_rectangle_sum(strip_start_row + 1, piece_start_col, current_row, col);，唯有strip_start_row需要加1，因为它表示上一个已完成条带的最后一行，是一个边界标记，不包含在当前条带中。当前条带实际从strip_start_row + 1开始。

答案

思考

这个解题思路避免了DP，用前缀和解决了大量的重复计算。而贪心和二分的结合，可以加速我们找到最大最小值的速度。