學生成績計算 題解|APCS 2026 年 6 月中級 第 1 題


簡潔題意

\(N\) 位學生(\(N \le 100\)),第 \(i\) 位有 \(k_i\) 個成績(\(3 \le k_i \le 10\),成績 \(0 \sim 100\))。每位學生的總成績:成績由小到大排好,去掉最高的 \(x\) 個、最低的 \(y\) 個(\(0 \le x, y \le 1\)),剩下的取平均、小數捨去。輸出總成績最高的學生編號與總成績;同分輸出編號最小的。\(x\)、\(y\) 在輸入的最後一行。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(20\) 分):\(N = 1\)。
  • 子題組 2(\(30\) 分):\(x = 0\) 且 \(y = 0\)。
  • 子題組 3(\(50\) 分):無額外限制。

先拿下子題組 2(30 分):不去掉成績,先把擂台寫對

子題組 1 只有一位學生,但最高、最低成績照樣要去掉;不用去掉任何成績的子題組 2 反而最好拿。

\(x = y = 0\) 時不用去掉任何成績,總成績就是總和除以 \(k\)。成績都不是負數,整數除法 sum / k 就是把小數捨去(2.6)。一邊讀一邊加總,不用排序,也不用把成績存起來。

找最高分用 3.12 的擂台法,兩個細節:

  • 擂台初值設 \(-1\)。總成績最低是 \(0\),初值設 \(0\) 的話,每個人都是 \(0\) 分時一個人也換不上去,印出來的編號是初值。
  • 嚴格大於才換人。同分時不換,留在台上的就是編號小的那一位。
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int bestId = 0, bestTotal = -1;  // 擂台初值 -1:比任何總成績都小
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        int sum = 0;
        for (int j = 0; j < k; j++) {
            int score;
            cin >> score;
            sum += score;
        }
        int total = sum / k;  // 成績都不是負數:整數除法就是捨去小數
        if (total > bestTotal) {  // 嚴格大於才換:同分留下編號小的
            bestTotal = total;
            bestId = i;
        }
    }
    cout << bestId << ' ' << bestTotal << '\n';  // 子題組 2 的 x、y 都是 0,不用讀
    return 0;
}

這個版本對範例 1 會 WA 是正常的;它對子題組 2 的 \(6\) 筆全對,穩拿 \(30\) 分。

從 30 分到 100 分:每個人先排序,再去頭去尾

\(x\)、\(y\) 在最後一行,讀到它們之前不知道要去掉幾個,所以先把成績存起來。每個人的成績個數不一樣,就照最多的 \(10\) 個開二維陣列(6.9):第 \(i\) 列 scores[i] 存第 \(i\) 位的成績,cnt[i] 記他有幾個。排序寫成 sort(scores[i], scores[i] + k),只排這一列的前 \(k\) 個。

每個人做三件事:

  1. 排序。「最高的 \(x\) 個」看的是分數大小,不是輸入的順序。
  2. 取中間那一段。排好之後去掉前 \(y\) 個、後 \(x\) 個,剩下第 \(y\) 個到第 \(k - x - 1\) 個(從 \(0\) 數起),共 \(k - x - y\) 個。照位置去掉,同分的成績只會去掉一個:範例 1 的第 \(3\) 位有兩個 \(100\),只去掉其中一個。\(k \ge 3\) 而 \(x + y \le 2\),至少剩一個,不會除以 \(0\)。
  3. 除以剩下的個數 \(k - x - y\),不是 \(k\)。

擂台和子題組 2 的版本一樣。\(x\)、\(y\) 最多是 \(1\),所以也可以不排序:總和減掉最大值(\(x = 1\) 時)、減掉最小值(\(y = 1\) 時)。

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 105;     // N ≤ 100,編號從 1 開始
const int MAX_K = 15;      // 每位最多 10 個成績
int scores[MAX_N][MAX_K];  // scores[i]:第 i 位學生的成績
int cnt[MAX_N];            // cnt[i]:第 i 位學生有幾個成績

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        cnt[i] = k;
        for (int j = 0; j < k; j++) {
            cin >> scores[i][j];
        }
    }
    int x, y;  // x:去掉最高的個數;y:去掉最低的個數
    cin >> x >> y;

    int bestId = 0, bestTotal = -1;
    for (int i = 1; i <= n; i++) {
        int k = cnt[i];
        sort(scores[i], scores[i] + k);  // 由小到大:最低的在前面、最高的在後面
        int sum = 0;
        for (int j = y; j < k - x; j++) {  // 跳過前 y 個、後 x 個
            sum += scores[i][j];
        }
        int total = sum / (k - x - y);  // 除以剩下的個數
        if (total > bestTotal) {
            bestTotal = total;
            bestId = i;
        }
    }
    cout << bestId << ' ' << bestTotal << '\n';
    return 0;
}

測過再交:範例的 \(x\) 和 \(y\) 都一樣

兩個範例都是 \(x = y\),每個人的平均都是整數,總成績最高的也只有一位。下面五種錯法範例都會過(見常犯錯誤),自己補這幾筆:

輸入 正確輸出 這一筆在測什麼
1/3 1 1 0/1 0 1 0 \(x \ne y\):只去掉最高的 \(1\);最低的 \(0\) 排在最後面,要先排序
1/3 0 1 1/0 1 1 1 只去掉最低的 \(0\)
2/3 0 0 0/3 0 0 1/0 0 1 0 第 \(2\) 位的平均比較高,但捨去小數後兩人都是 \(0\):同分選編號小的

三筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 沒排序,照輸入的順序去掉頭尾:範例全過,自測表第 1 列印 1 1;本站 \(20\) 筆掛 \(13\) 筆。
  • \(x\)、\(y\) 用反:範例的 \(x\)、\(y\) 一樣,所以全過;自測表第 2 列印 1 0,本站 \(20\) 筆掛 \(9\) 筆。
  • 用 double 算平均、比大小,輸出時才捨去:捨去後同分的兩人,平均比較高的會被選上。範例全過,自測表第 3 列印 2 0;本站 \(20\) 筆掛 \(9\) 筆。
  • 同分也換人(>=):留下的是編號大的。範例全過,自測表第 3 列印 2 0;本站 \(20\) 筆掛 \(13\) 筆。
  • 擂台初值設 \(0\):每個人的總成績都是 \(0\) 時一個人也換不上去。範例全過,自測表第 3 列印 0 0;本站 \(20\) 筆掛 \(3\) 筆。