杭電 2014 青年歌手大獎賽：去極值平均分計算（冒泡排序/選擇排序實現）

題目描述

輸入多組測試數據。每組第一個整數 n (2 < n ≤ 100) 為評委數，隨後 n 個分數。去掉一個最高分和一個最低分，計算剩餘 n-2 個分數的平均值，保留兩位小數輸出。

解題思路

1. 讀入 n 與分數數組
2. 排序（升序或降序均可）
3. 求和 sum = a[1] + ... + a[n-2]（去掉 a[0] 和 a[n-1]）
4. 平均值 avg = sum / (n-2)
5. 輸出 printf("%.2f\n", avg)

完整代碼（冒泡排序版）

#include <stdio.h>

int main() {
    int n, i, j;
    double a[100], sum;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; ++i) scanf("%lf", &a[i]);
        // 冒泡排序：升序
        for (i = 0; i < n-1; ++i)
            for (j = 0; j < n-i-1; ++j)
                if (a[j] > a[j+1]) {
                    double t = a[j];
                    a[j] = a[j+1];
                    a[j+1] = t;
                }
        sum = 0;
        for (i = 1; i < n-1; ++i) sum += a[i];
        printf("%.2lf\n", sum / (n-2));
    }
    return 0;
}

優化版（選擇排序 / 庫函數）

#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    int n, i;
    double a[100], sum;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; ++i) scanf("%lf", &a[i]);
        sort(a, a+n);  // STL sort，O(n log n)
        sum = 0;
        for (i = 1; i < n-1; ++i) sum += a[i];
        printf("%.2lf\n", sum / (n-2));
    }
    return 0;
}

關鍵細節

• 輸入結束：while(scanf("%d",&n)!=EOF) 處理多組數據
• 數組大小：n ≤ 100，開 100 足夠
• 浮點輸出：%.2lf 保留兩位小數，四捨五入
• 去極值：排序後直接跳過首尾，或用 max_element/min_element 找出最大最小值減去（無需排序，O(n)）

無需排序的 O(n) 做法

double sum = 0, mx = -1, mn = 101;
for (i = 0; i < n; ++i) {
    scanf("%lf", &a[i]);
    sum += a[i];
    if (a[i] > mx) mx = a[i];
    if (a[i] < mn) mn = a[i];
}
printf("%.2lf\n", (sum - mx - mn) / (n-2));

本題屬於入門級模擬題，考察基本輸入輸出、排序/極值查找、浮點運算格式化。掌握多種實現方式（冒泡、選擇、STL、單趟掃描），可根據數據規模靈活選擇。