ACM 題目分步求解：課程平均分調整問題的數學建模與優化

問題重述

給定學生選課成績矩陣（未選為 0），對某課程所有選課學生成績加 delta，使調整後該課程平均分等於「選修該課程的所有學生」的「所有課程平均分」的平均值。求 delta。

數學推導

設：

• n：選修該課學生數
• y_i：第 i 位學生該課原始成績
• avg_i：第 i 位學生所有選修課程的平均分
• target = (Σ avg_i) / n

調整後該課平均：(Σ(y_i + delta)) / n = (Σ y_i)/n + delta

令等於 target：

delta = target - (Σ y_i)/n
      = (Σ avg_i - Σ y_i) / n
      = (Σ(avg_i - y_i)) / n

優化實作：預計算學生平均分

#include <stdio.h>

#define MAX_STU 20
#define MAX_CLS 10

int main(void) {
    int stu_n, cls_n;
    scanf("%d %d", &stu_n, &cls_n);

    char cls_name[MAX_CLS][16];
    int score[MAX_STU][MAX_CLS] = {0};
    double stu_avg[MAX_STU] = {0};

    for (int i = 0; i < cls_n; ++i) scanf("%s", cls_name[i]);
    for (int i = 0; i < stu_n; ++i)
        for (int j = 0; j < cls_n; ++j)
            scanf("%d", &score[i][j]);

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

    // 各課程計算 delta
    for (int c = 0; c < cls_n; ++c) {
        int sum_y = 0, cnt = 0;
        double sum_avg = 0;
        for (int s = 0; s < stu_n; ++s) {
            if (score[s][c] != 0) {
                sum_y += score[s][c];
                sum_avg += stu_avg[s];
                ++cnt;
            }
        }
        if (cnt == 0) { printf("%s 0\n", cls_name[c]); continue; }
        double delta = (sum_avg - sum_y) / cnt;
        printf("%s %.2f\n", cls_name[c], delta);
    }
    return 0;
}

複雜度對比

ACM 解題心法

1. 數學建模 → 化簡公式
2. 找出重複計算 → 預處理/備忘錄
3. 邊界條件：無人選課、分母為零
4. 輸出格式嚴格對題目要求