ACM 題目分步求解：課程成績調整與平均值計算

問題重述

給定學生-課程成績矩陣（0 代表未選修），對每門課程計算一個 delta，使「選修該課程的學生，成績各加 delta 後的平均分」等於「這些學生所有課程平均分的平均值」。輸出每門課程的 delta。

數學推導

設：

• 選修該課程的學生集合為 S，人數 k = |S|。
• 學生 i ∈ S 在該課程原始成績 y_i。
• 學生 i 所有選修課程的平均分 avg_i = (Σ_j score_{i,j}) / cnt_i。
• 目標：(Σ_{i∈S} (y_i + delta)) / k = (Σ_{i∈S} avg_i) / k

解得：

delta = (Σ avg_i - Σ y_i) / k
      = (sum_avg - total_course_score) / count_selected

分步實作策略

1. 預先計算每位學生的平均分 student_avg[i]，避免重複迴圈（原始碼中嵌套循環導致 O(S×C²)）。
2. 遍歷每門課程，累加選修生的 student_avg 與該課原始成績。
3. 套用公式計算 delta。

優化後 C 實作

#include 

#define MAX_STU 20
#define MAX_CRS 10

int main(void) {
    int stu_n, crs_n;
    if (scanf("%d %d", &stu_n, &crs_n) != 2) return 0;

    char crs_name[MAX_CRS][16];
    for (int i = 0; i < crs_n; i++) scanf("%s", crs_name[i]);

    int score[MAX_STU][MAX_CRS];
    for (int i = 0; i < stu_n; i++)
        for (int j = 0; j < crs_n; j++)
            scanf("%d", &score[i][j]);

    // 步驟 1：預計算每位學生平均分
    double stu_avg[MAX_STU] = {0};
    for (int i = 0; i < stu_n; i++) {
        int sum = 0, cnt = 0;
        for (int j = 0; j < crs_n; j++) {
            if (score[i][j] != 0) { sum += score[i][j]; cnt++; }
        }
        stu_avg[i] = cnt ? (double)sum / cnt : 0.0;
    }

    // 步驟 2：逐門課程計算 delta
    for (int c = 0; c < crs_n; c++) {
        double sum_avg = 0;   // Σ avg_i
        int total_score = 0;  // Σ y_i
        int cnt = 0;          // k

        for (int s = 0; s < stu_n; s++) {
            if (score[s][c] != 0) {
                sum_avg += stu_avg[s];
                total_score += score[s][c];
                cnt++;
            }
        }

        int delta = cnt ? (int)((sum_avg - total_score) / cnt) : 0;
        printf("%s %d\n", crs_name[c], delta);
    }
    return 0;
}

複雜度比較

測試樣例

輸入:
3 2
Math Physics
80 90
70 0
0 60

學生平均: (85, 70, 60)
Math: 選修生 0,1 → avg=(85+70)/2=77.5, 總分=150 → delta=(155-150)/2=2
Physics: 選修生 0,2 → avg=(85+60)/2=72.5, 總分=150 → delta=(145-150)/2=-2

輸出:
Math 2
Physics -2

總結

「分步實現、打基礎、再優化」是解題通法：先寫出正確但可能低效的版本，識別重複計算熱點，引入中間陣列/快取消除冗餘，最終達到最優複雜度。此題核心在於「預計算學生平均分」將 O(Crs²) 降為 O(Crs)。