HDU 1205 吃糖果：鴿巢原理判斷能否不重複相鄰吃完所有糖果

問題大意

N 種糖果，第 i 種有 m_i 顆。每次吃一顆，不能連續吃同一種。問是否存在吃完所有糖果的順序。

鴿巢原理判斷條件

設數量最多的糖果有 max 顆，其餘糖果總和 sum - max。將最多的糖果作為「隔板」，形成 max+1 個空隙（含兩端）。要使其不相鄰，至少需要 max-1 顆其他糖果填充中間空隙。

充要條件：sum - max ≥ max - 1，即 sum ≥ 2*max - 1

證明直觀理解

最多糖果 M M M M M 需 4 個其他糖果隔開：M X M X M X M X M。其他糖果總數若 ≥ 4，總能插入；若 < 4，必有兩個 M 相鄰。其他糖果數量較少，總能插入已構造的間隙中（因為其數量 ≤ max）。

代碼實現

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        ll sum = 0, mx = 0, x;
        for (int i=0; i= mx - 1 ? "Yes" : "No");
    }
    return 0;
}

樣例

輸入:
2
3
4 1 1
5
5 4 3 2 1

輸出:
No
Yes

Case 1: sum=6, max=4 → 6-4=2 < 3 → No
Case 2: sum=15, max=5 → 15-5=10 ≥ 4 → Yes

複雜度

• 時間：O(N) 每測試用例
• 空間：O(1)