Codeforces 134C - Swaps：優先隊列模擬循環桌面交換

問題重述

n 人圍圓桌，第 i 人初始持有 s 張顏色 i 的卡片。規則：

1. 只能給出自己顏色的卡片
2. 不能接收已擁有的顏色（含自己顏色）
3. 每次交換雙方各給一張、收一張

目標：所有人給出所有初始卡片。判斷是否可能，可能則輸出交換序列。

關鍵觀察

本質是構造一個有向多重圖的歐拉迴路分解。每人出度 = 初始卡片數，入度 = 總卡片數 - 初始卡片數。條件：總卡片數為 n 的倍數（題目給定 s 滿足），且無人初始卡片數 > 總卡片數/2（否則無法給出）。

貪心 + 優先隊列構造

維護「還有卡片可給」的人的最大堆（按剩餘卡片數）。每次取出前兩人 u, v 進行交換，剩餘數 -1，若仍 > 0 重新入堆。類似 Havel-Hakimi 構造圖。

代碼框架（核心邏輯）

struct Node { int id, left; };
bool operator<(Node a, Node b) { return a.left < b.left; } // 大根堆

priority_queue pq;
for (i=1..n) if (a[i]>0) pq.push({i, a[i]});

vector> swaps;
while (pq.size() >= 2) {
    Node u = pq.top(); pq.pop();
    Node v = pq.top(); pq.pop();
    swaps.push_back({u.id, v.id});
    if (--u.left > 0) pq.push(u);
    if (--v.left > 0) pq.push(v);
}
if (!pq.empty()) { // 還有剩餘無法配對
    cout << "No\n";
} else {
    cout << "Yes\n" << swaps.size() << "\n";
    for (auto [x,y] : swaps) cout << x << ' ' << y << "\n";
}

複雜度

• 時間：O(s log n)，s ≤ 200000
• 空間：O(n + s)

注意

原題輸入給出每人當前卡片數（非初始），需先驗證總和是否為 n*s 並推導初始分佈。完整代碼較長，此處給出核心構造邏輯。