Timus 1935 Tears of Drowned：貪心排序求最小書頁數

問題描述

有 n 張蝙蝠皮 (1 ≤ n ≤ 100)，第 i 張要求其左右兩側各至少有 aᵢ 頁書頁隔開。所有皮夾在一本書中，求書的最小總頁數。

樣例分析

輸入：3
5 10 3
輸出：28

最優排序：3, 5, 10（升序）。
頁數計算：

左封面 3 頁
+ max(3,5) = 5 頁 (3號皮右側 / 5號皮左側共用)
+ max(5,10) = 10 頁
+ 右封面 10 頁
= 3 + 5 + 10 + 10 = 28

通式：排序後，總頁數 = a₁ + Σ max(aᵢ, aᵢ₊₁) + aₙ = Σ aᵢ + max(aᵢ)。
因為 max(a,b) = a + b - min(a,b)，求和後內部項各出現 2 次，兩端各 1 次，等價於 sum + max。

證明排序最優

任意相鄰逆序對 ... x, y ... (x > y)。交換為 y, x：
原貢獻：max(prev, x) + max(x, y) + max(y, next)
新貢獻：max(prev, y) + max(y, x) + max(x, next)
因 max(x,y)=max(y,x)，且 max(prev,y) ≤ max(prev,x)、max(x,next) ≤ max(y,next) (x>y)，新排列不劣。
故升序排列全局最優。

程式碼實現（C++）

/* Timus 1935 Tears of Drowned */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    long long sum = 0, mx = 0;
    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        sum += a;
        mx = max(mx, (long long)a);
    }
    cout << sum + mx << "\n";
    return 0;
}

關鍵洞察

• 題目未固定皮的順序，可任意排列（易誤以為按輸入順序）。
• 最優策略：升序排列，使較小需求被較大需求「吸收」（共用頁面）。
• 最終公式極簡：sum(a) + max(a)，無需顯式排序（但理解排序證明至關重要）。

總結

Timus 1935 是貪心排序 + 數學化簡的漂亮題目。陷阱在於「順序可調整」與「共用頁面」的雙重直覺衝突。最終公式 sum + max 既優雅又高效，體現了「理解問題本質勝過複雜實現」的算法哲學。