CodeForces 545D Queue：排序貪心策略解決失望人數最小化

題目大意

有 n 人排隊，每人有一個最大等待時間 a[i]。若某人前面所有人的等待時間總和超過其 a[i]，該人會失望。可重新排序隊列，求最多有多少人不失望。

貪心證明

為讓盡量多人不失望，應優先安排等待時間短的人。證明：若存在逆序對 a[i] > a[j] 且 在 j 前，交換兩人不會增加失望人數，反而可能減少。故最優策略是按等待時間升序排列。

算法步驟

1. 讀入 n 及陣列 a。
2. 升序排序 a。
3. 遍歷累加前綴和 sum，若 a[i] >= sum 則該人不失望，計數 ans++ 並 sum += a[i]；否則跳過（該人失望，不加入前綴和）。

C++ 代碼

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    sort(a.begin(), a.end());
    long long sum = 0, ans = 0;
    for (auto x : a) {
        if (x >= sum) {
            ++ans;
            sum += x;
        }
    }
    cout << ans << '\n';
    return 0;
}

複雜度

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

總結

經典貪心題：排序後模擬前綴和，直觀且最優。注意使用 long long 防止溢位。