Codeforces 439B 解題報告：最小化教學時間

題目大意

給定一個學生需要學習 n 門課程，每門課程包含若干章節。學習第一門課程的每個章節需要 x 小時，之後每學完一門課程，後續課程的每章節學習時間減少 1 小時（最少 1 小時）。目標是安排課程順序，使總教學時間最短。

核心思路

這是一道典型的貪心問題。為了讓總時間最小，應優先安排章節數較少的課程在前面學習，因為前期單位章節耗時較高；將章節數較多的課程放在後面，享受較低的單位時間成本。因此，只需將所有課程的章節數按升序排序，依序累加時間即可。

關鍵實現細節

資料範圍較大，答案可能超過 32 位整數範圍，必須使用 long long（或 C++11 的 int64_t）儲存答案與中間變數。作者曾因僅將 ans 宣告為 long long 而忽略了 x 等變數也需擴大型別，導致被 hack。良好的習慣是：涉及大數運算時，相關變數統一使用 64 位整數。

參考代碼 (C++)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;
    vector<long long> c(n);
    for (int i = 0; i < n; ++i) cin >> c[i];
    sort(c.begin(), c.end());

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += c[i] * x;
        if (x > 1) --x;
    }
    cout << ans << endl;
    return 0;
}

複雜度分析

• 時間複雜度：O(n log n)，主要來自排序。
• 空間複雜度：O(n)，儲存章節數陣列。

總結

本題考察基本貪心策略與資料型別選擇的細心度。排序後依序處理，邏輯清晰，代碼簡潔，是入門級貪心題的優秀範例。