ACM 經典題解：偶數求和（山東理工大學 1242）

題目描述

給定長度 n (n≤100) 的遞增偶數數列：2, 4, 6, ..., 2n。要求每 m 個數計算一次平均值，不足 m 個則以實際個數計算平均。輸出所有平均值序列，每組測資佔一行。

輸入輸出範例

輸入：
3 2
4 2

輸出：
3 6
3 7

說明：
n=3, m=2 → 數列 2,4,6 → 分組 (2,4) 平均 3、(6) 平均 6。
n=4, m=2 → 數列 2,4,6,8 → 分組 (2,4) 平均 3、(6,8) 平均 7。

解題思路

1. 讀取多組 n, m 直到 EOF。
2. 計算完整群組數 r = n / m 與剩餘個數 l = n % m。
3. 依序累加偶數（從 2 開始，每次 +2），每累積 m 個輸出平均；最後剩餘 l 個另行計算平均。
4. 注意輸出格式：每組測資一行，數值間單一空格，行尾無多餘空格。

參考程式碼（C 語言）

#include <stdio.h>

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        int total_groups = n / m;
        int remainder = n % m;
        int current = 2;           // 起始偶數
        long sum = 0;
        int count = 0;
        int first_output = 1;

        // 處理完整群組
        for (int g = 0; g < total_groups; ++g) {
            sum = 0;
            for (int i = 0; i < m; ++i) {
                sum += current;
                current += 2;
            }
            if (!first_output) printf(" ");
            printf("%ld", sum / m);
            first_output = 0;
        }

        // 處理剩餘元素
        if (remainder > 0) {
            sum = 0;
            for (int i = 0; i < remainder; ++i) {
                sum += current;
                current += 2;
            }
            if (!first_output) printf(" ");
            printf("%ld", sum / remainder);
        }
        printf("\\n");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n)，每個偶數僅被訪問一次。
• 空間複雜度：O(1)，僅使用常數額外變數。

常見錯誤提醒

• 整數除法直接取商，題目保證平均值為整數（偶數和除以個數必為整數）。
• 輸入可能包含多行測資，需以 while(scanf(...)!=EOF) 迴圈處理。
• 輸出格式嚴格：行尾無空格，組間單一空格。