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

🔗 🟢 CF1774D. Same Count One

Problem Statement

題目簡述

給定 $n$ 個長度為 $m$ 的二進位陣列。每次操作可以選擇兩個陣列 $x, y$ 和一個位置 $pos$ ，交換 $a_{x,pos}$ 和 $a_{y,pos}$ 。

求使所有陣列中 $1$ 的個數相同所需的最少操作次數，並輸出交換方案。若無法達成則輸出 $-1$ 。

Constraints

約束條件

$2 \le n, m \le 10^5$
$a_{i,j} \in \{0, 1\}$
$\sum n \cdot m \le 10^6$

思路：貪心逐位置配對交換

可行性判斷

首先計算所有陣列的 $1$ 的總數 $\text{tot} = \sum_{i=1}^{n} \text{cnt}_i$ 。若 $\text{tot} \mod n \neq 0$ ，則無法使每個陣列的 $1$ 數量相等，輸出 $-1$ 。

否則，目標是使每個陣列的 $1$ 數量等於 $\text{avg} = \text{tot} / n$ 。

貪心策略

核心觀察

交換操作只在不同陣列的同一個位置進行，因此我們可以 按照位置獨立處理。

對於每一個位置 $j$ ：

找出所有「多餘」的陣列：當前位置為 $1$ 且該陣列 $1$ 的總數超過 $\text{avg}$
找出所有「缺少」的陣列：當前位置為 $0$ 且該陣列 $1$ 的總數低於 $\text{avg}$
將這兩類陣列 一一配對進行交換

正確性證明

我們將所有陣列根據初始 $1$ 的數量分為三類：

多餘陣列 ( $S_{>}$ )：初始 $1$ 的數量 $> \text{avg}$ 。這類陣列在過程中只會減少 $1$ ，直到數量等於 $\text{avg}$ 。
缺少陣列 ( $S_{<}$ )：初始 $1$ 的數量 $< \text{avg}$ 。這類陣列在過程中只會增加 $1$ ，直到數量等於 $\text{avg}$ 。
平衡陣列 ( $S_{=}$ )：初始 $1$ 的數量 $= \text{avg}$ 。這類陣列全程不參與交換。

根據反證法，演算法結束後，不可能存在某個陣列 $A \in S_{>}$ 未達到目標，反之亦然。

證明細節

反證法：假設演算法結束後，仍有某個陣列 $A \in S_{>}$ 未達到目標（即最終 $cnt[A] > \text{avg}$ ）。
根據總數守恆，必然存在某個陣列 $B \in S_{<}$ 也未達到目標（即最終 $cnt[B] < \text{avg}$ ）。

由於最終 $cnt[A] > \text{avg} > cnt[B]$ ，必然存在某一個位置 $j$ ，使得 $grid[A][j] = 1$ 且 $grid[B][j] = 0$ 。

回顧演算法在處理位置 $j$ 時的狀態：

陣列 $A$ 屬於 $S_{>}$ ， $cnt$ 只減不增，且最终 $> \text{avg}$ ，故處理位置 $j$ 時 $cnt[A] > \text{avg}$ 。均滿足條件，應被加入候選名單 arr1。
陣列 $B$ 屬於 $S_{<}$ ， $cnt$ 只增不減，且最终 $< \text{avg}$ ，故處理位置 $j$ 時 $cnt[B] < \text{avg}$ 。均滿足條件，應被加入候選名單 arr2。

演算法會將 arr1 與 arr2 盡可能配對。

若 $A$ 未被交換，意味著 arr2 空了（ $B$ 被配對走了）。
若 $B$ 未被交換，意味著 arr1 空了（ $A$ 被配對走了）。

這產生了矛盾： $A$ 和 $B$ 不可能在同一位置 $j$ 都「剩下」且未被處理。因此假設不成立，演算法必能使所有陣列達到平均值 $\text{avg}$ 。

複雜度分析

時間複雜度： $\mathcal{O}(nm)$
空間複雜度： $\mathcal{O}(nm)$

Code

def solve():
    n, m = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(n)]

    cnt = [sum(row) for row in grid]
    tot = sum(cnt)
    if tot % n:
        print(-1)
        return -1
    avg = tot // n

    ops = []
    for j in range(m):
        arr1 = []
        arr2 = []
        for i in range(n):
            if grid[i][j] == 1 and cnt[i] > avg:
                arr1.append(i)
            elif grid[i][j] == 0 and cnt[i] < avg:
                arr2.append(i)
        for i1, i2 in zip(arr1, arr2):
            ops.append((i1 + 1, i2 + 1, j + 1))
            grid[i1][j] = 0
            grid[i2][j] = 1
            cnt[i1] -= 1
            cnt[i2] += 1
    
    print(len(ops))
    for i1, i2, j in ops:
        print(i1, i2, j)
    assert all(sum(row) == avg for row in grid)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()