題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P3017 [USACO11MAR] Brownie Slicing G

Problem Statement

題目簡述

給定一個大小為 $R \times C$ 的整數矩陣，其中 $N_{ij}$ 代表第 $i$ 橫列(row) 第 $j$ 直行(column) 的分數。

你需要對這個矩陣進行切割：先水平切 $A-1$ 刀，再對這 $A$ 個切分出來的矩陣分別獨立地垂直切 $B-1$ 刀，將矩陣分成 $A \times B$ 個小塊。每一刀必須切在格子之間（即切出完整行或列）。定義每一塊的「分數」為該子矩陣內所有數字的總和。

定義每一塊的「分數」為該子矩陣內所有數字的總和。目標是讓這些 $A \times B$ 塊中分數最小的一塊儘量大。輸出這個最大可能的最小值。

Constraints

約束條件

$1 \le R, C \le 500$
$1 \le A \le R$
$1 \le B \le C$
$0 \le N_{ij} \le 4 \cdot 10^4$

思路：二分答案 + 貪心 + 二維前綴和

這是一個典型的「最大化最小值」問題，這類問題通常可以透過二分搜尋答案來解決。
我們將問題轉化為判定性問題：給定一個目標分數 $mid$ ，判斷是否能將矩陣切成 $A \times B$ 塊，且每一塊的分數都大於等於 $mid$ 。

貪心判定策略

為了判斷是否能切出符合條件的區塊，我們可以採用貪心策略，由上而下、由左至右進行嘗試：

尋找合法的水平區塊：我們由上往下逐列擴展當前的水平範圍。對於每一個水平範圍，我們嘗試在其中進行垂直切割。
尋找合法的垂直區塊：在固定的水平範圍內，我們由左往右逐行擴展當前的垂直範圍。一旦發現當前累積的子矩陣分數大於等於 $mid$ ，我們就貪心地切一刀，並重新開始計算下一個垂直區塊。
確認水平切割：如果在當前的水平範圍內，我們能夠成功切出至少 $B$ 個分數大於等於 $mid$ 的區塊，這意味著我們找到了一個合法的水平切分。此時，我們就可以確定這一刀水平切割，並繼續往下尋找下一個水平區塊。
擴展水平範圍：如果當前的水平範圍無法切出 $B$ 個合法的區塊，我們就必須繼續往下包含更多的橫列，直到滿足條件為止。

如果在掃描完所有橫列後，我們能夠成功切出至少 $A$ 個合法的水平區塊，就代表當前的目標分數 $mid$ 是可行的。

貪心的正確性

為什麼可以貪心？因為矩陣中的數字都是非負整數，子矩陣的範圍越大，分數只會增加不會減少。因此，一旦滿足條件就立刻切割，可以為後面的區塊保留最多的剩餘空間，這是最優的策略。

快速計算區塊分數

在貪心判定的過程中，我們需要頻繁地計算某個子矩陣的分數總和。為了避免每次都重新遍歷子矩陣，我們可以預先計算二維前綴和。
透過二維前綴和，我們可以在 $\mathcal{O}(1)$ 的時間內查詢任意子矩陣的分數總和，這能大幅提升判定函數的執行效率。

複雜度分析

時間複雜度： $\mathcal{O}(R \cdot C \log(\frac{S}{A \cdot B}))$ $O (R \cdot C lo g (\frac{S}{A \cdot B}))$ ，其中 $S$ $S$ 為整個矩陣的總分數。
- 預處理二維前綴和需要 $\mathcal{O}(R \cdot C)$ 的時間。
- 因為最小塊的最大值不可能超過平均分數，否則總和會超過 $S$ ，因此二分搜尋的上界為平均分數的下取整 $\lfloor S/(A \cdot B) \rfloor$ ，二分搜尋的次數約為 $\log(\frac{S}{A \cdot B})$ 次。
- 每次判定時，雖然有巢狀迴圈，但水平和垂直的邊界指標都是單調遞增的（類似雙指標的概念），因此單次判定的時間複雜度為 $\mathcal{O}(R \cdot C)$ 。
空間複雜度： $\mathcal{O}(R \cdot C)$ ，主要用於儲存二維前綴和陣列。

垂直邊界查找的另一種選擇

在固定水平區間內尋找垂直切割點時，也可以採用二分搜尋的方式：對於給定的左邊界，二分查詢滿足區塊和 $\ge mid$ 的最左側右邊界位置。由於共需切出 $B$ 個區塊，內層需要進行 $B$ 次二分，每次二分需 $\mathcal{O}(\log C)$ 時間計算前綴和，因此單次 $check$ 的時間複雜度為 $\mathcal{O}(R \cdot B \log C)$ 。

當 $B$ 遠小於 $C$ 時，此方法可能比雙指標的 $\mathcal{O}(R \cdot C)$ 更快。但本題中 $R, C \le 500$ ，且 $B$ 最大可達 $C$ ，因此反而是種負優化。

Code

def solve():
    R, C, A, B = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(R)]

    s = [[0] * (C + 1) for _ in range(R + 1)]
    for i, row in enumerate(grid, start=1):
        for j, val in enumerate(row, start=1):
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + val

    def area(x1, x2, y1, y2):
        return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

    tot = sum(sum(row) for row in grid)

    def check(mid):
        x1 = x2 = 1
        cntx = 0
        while x2 <= R:
            y1 = y2 = 1  # Two pointers
            cnty = 0
            while y1 <= C:
                # 二分需要 O(B log C) 次，而雙指標需要 O(C) 次，如果 B 遠比 C 小的話可以考慮二分
                # y2 = bisect_left(range(C + 1), mid, key=lambda y2: area(x1, x2, y1, y2))
                while y2 <= C and area(x1, x2, y1, y2) < mid:
                    y2 += 1
                if y2 > C:
                    break
                # assert area(x1, x2, y1, y2) >= mid
                cnty += 1
                if cnty == B:
                    break
                y1 = y2 = y2 + 1
            if cnty == B:
                cntx += 1
                if cntx == A:
                    return True
                x1 = x2 = x2 + 1
            else:
                x2 += 1
        return False

    left, right = 0, tot // (A * B)
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            left = mid + 1
        else:
            right = mid - 1
    print(right)


if __name__ == "__main__":
    solve()