Codeforces 549G Happy Line：貪心+排序的塔模型巧解

問題重述

n (≤ 200,000) 人排隊買冰淇淋，第 i 人（從隊尾數起）有 aᵢ 元。任意相鄰兩人 a（後）與 b（前），a 可付 1 元給 b 交換位置（a 錢-1，b 錢+1）。目標：調整順序使隊列非嚴格遞增（即前面的人錢數 ≥ 後面的人），輸出最終每人錢數；不可能則輸出 :(。

關鍵洞察：塔與樓梯模型

將每人看作一座塔，高度為其錢數；隊列位置看作樓梯，第 i 階高度為 i（從隊尾 0 開始）。人站在樓梯上時，其「實際高度」= 塔高 + 樓梯高 = aᵢ + i。

交換操作：後人塔移到前一階，前人塔移到後一階。塔高不變，樓梯高互換。因此「實際高度」aᵢ + i 不變！

推論

• 最終隊列非嚴格遞增 ⇔ 最終塔高序列非嚴格遞增。
• 塔的相對順序不變（只能相鄰交換），但每座塔可上下移動樓梯。
• 為使最終塔高非嚴格遞增，只需將所有塔按 aᵢ + i 從小到大排序，依次放在樓梯 0,1,2... 上。
• 第 i 位最終錢數 = 排序後第 i 個 (aⱼ + j) - i。

算法步驟

1. 讀入 n 和數組 a（下標 0 為隊尾）。
2. 計算 b[i] = a[i] + i。
3. 對 b 升序排序。
4. 檢查：若存在 b[i] - i < b[i-1] - (i-1)（即最終錢數非遞增），則無解，輸出 :(。
5. 否則輸出 b[i] - i（即最終從隊尾到隊首的錢數）。

樣例演示

輸入： 3 / 12 3 3
b = [12+0, 3+1, 3+2] = [12, 4, 5]
排序後 b = [4, 5, 12]
最終錢數 = [4-0, 5-1, 12-2] = [4, 4, 10] ✓

正確性證明

不變量：每人 aᵢ + i 恆定。最終隊列非嚴格遞增 ⇔ 最終 aᵢ 非嚴格遞增 ⇔ bᵢ - i 非嚴格遞增 ⇔ bᵢ 非嚴格遞增（因 i 嚴格遞增）。故只需將 b 排序。若排序後 bᵢ - i 仍非遞增，說明無法滿足條件。

複雜度

• 時間：O(n log n)（排序主導）。
• 空間：O(n)。

參考代碼

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if(!(cin >> n)) return 0;
    vector b(n);
    for (int i = 0; i < n; i++) {
        long long a; cin >> a;
        b[i] = a + i;
    }
    sort(b.begin(), b.end());
    for (int i = 1; i < n; i++) {
        if (b[i] - i < b[i-1] - (i-1)) {
            cout << ":(\n";
            return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << b[i] - i << (i+1==n?'\n':' ');
    }
    return 0;
}

總結

本題通過「塔+樓梯」模型將交換操作轉化為不變量 aᵢ + i，巧妙避開了複雜的模擬，化歸為簡單的排序問題。體現了競賽編程中「尋找不變量、轉換視角」的核心思想。