HDU 1205 吃糖果：三角形不等式巧解

問題描述

有 N 種糖果，第 i 種有 M_i 顆。Gardon 吃糖果時不喜歡連續吃同一種，即相鄰兩次不能吃同種。問是否存在一種吃法吃完所有糖果。

數學建模

設總糖果數 S = ΣM_i，最大堆數量 Max。要能安排不相鄰，充要條件是：

$$ \text{Max} \le S - \text{Max} + 1 \quad \Leftrightarrow \quad 2 \times \text{Max} \le S + 1 $$

這等價於三角形不等式：最長邊不超過其他邊長度之和 + 1（首尾可相同視為環）。

算法

1. 讀入 N 和 M_i，計算總和 S 和最大值 Max。
2. 若 `2 * Max <= S + 1` 輸出 "Yes"，否則 "No"。
3. 特殊情況：N=1 時，只有 M_1=1 才為 "Yes"。

代碼 (C)

#include 
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int N; scanf("%d", &N);
        long long sum = 0, maxv = 0, x;
        for (int i = 0; i < N; ++i) {
            scanf("%lld", &x);
            sum += x;
            if (x > maxv) maxv = x;
        }
        if (N == 1) puts(x == 1 ? "Yes" : "No");
        else puts(2 * maxv <= sum + 1 ? "Yes" : "No");
    }
    return 0;
}

複雜度

時間 O(N)，空間 O(1)。N ≤ 1,000,000，M_i ≤ 1,000,000，用 64 位整數防溢出。

總結

看似複雜的調度問題，實則轉化為簡單的不等式判斷。關鍵在於將「不相鄰」建模為「最長邊 ≤ 其他邊和 + 1」，這是組合數學中經典的「重新排列不相鄰」條件。