山東理工大學ACM 1242：偶數求和 - C語言解題詳解

題目描述

有一個長度為 n（n ≤ 100）的數列，定義為從 2 開始的遞增偶數：2, 4, 6, ..., 2n。要求按順序每 m 個數求一個平均值，若最後不足 m 個，則按實際個數求平均。輸出這個平均值序列。

輸入格式

多組測試數據，每組一行，包含兩個正整數 n 和 m。

輸出格式

每組輸入輸出一行平均值序列，值之間用空格分隔。

範例

輸入範例

3 2
4 2

輸出範例

3 6
3 7

範例解析

3 2：數列 [2, 4, 6]，每 2 個一組 → (2+4)/2=3, 6/1=6 → 輸出 3 6
4 2：數列 [2, 4, 6, 8]，每 2 個一組 → (2+4)/2=3, (6+8)/2=7 → 輸出 3 7

解題思路

直接模擬生成偶數序列並分組求平均。由於 n ≤ 100，極其簡單。注意整數除法截斷特性，題目樣例輸出為整數，說明要求整數平均值（向下取整）。

參考代碼 (C語言)

#include <stdio.h>

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        int first = 1;
        for (int start = 1; start <= n; start += m) {
            int end = start + m - 1;
            if (end > n) end = n;
            int count = end - start + 1;
            // 第 k 個偶數是 2k，區間和 = 2 * (start + ... + end) = 2 * count * (start + end) / 2
            long long sum = (long long)count * (start + end);
            int avg = sum / count; // 整數除法
            if (!first) printf(" ");
            first = 0;
            printf("%d", avg);
        }
        printf("\n");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n/m) 組數，每組 O(1) 計算，總體 O(n)。
• 空間複雜度：O(1)。

注意事項

• 偶數序列第 k 項為 2k，區間和可用等差數列公式直接計算，無需逐項累加。
• 平均值為整數除法（向下取整），樣例驗證符合。
• 多組輸入以 EOF 結束，while(scanf(...) != EOF) 處理。
• 輸出格式：同行數字間單空格，行末無多餘空格。