Codeforces 507A：貪心選課問題的排序與模擬

題目大意

有 n 門課，第 i 門需 a_i 天準備。總共有 k 天。每天只能準備一門課，準備完即可參加考試。求最多能參加幾門考試，並輸出其原始下標（任意順序）。

貪心策略：按準備時間升序

為了在有限天數內完成最多課程，應優先選準備時間最短的課。
算法：

1. 將 (a_i, index) 存入結構體數組。
2. 按 a_i 升序排序。
3. 遍歷累加 a_i，直到總和 > k 停止。
4. 輸出已選課程的原始下標。

C++ 代碼

#include 
using namespace std;
struct Course { int time, idx; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    vector c(n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i].time;
        c[i].idx = i + 1;
    }
    sort(c.begin(), c.end(), [](Course a, Course b){ return a.time < b.time; });
    vector ans;
    for (auto &cr : c) {
        if (k < cr.time) break;
        k -= cr.time;
        ans.push_back(cr.idx);
    }
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    if (!ans.empty()) cout << '\n';
    return 0;
}

關鍵點

• 輸出下標而非值，故排序前必須保存原始索引。
• k 遞減模擬天數消耗，直觀易懂。
• 若所有課程總和 ≤ k，輸出所有下標。

總結

CF 507A 是「貪心 + 排序 + 索引保存」的入門題。核心洞察：單位資源產出最大化 → 選成本最小項目。同類題：CF 1490C、背包問題贪心變體。