學生成績計算 題解|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\) 個。
每個人做三件事:
- 排序。「最高的 \(x\) 個」看的是分數大小,不是輸入的順序。
- 取中間那一段。排好之後去掉前 \(y\) 個、後 \(x\) 個,剩下第 \(y\) 個到第 \(k - x - 1\) 個(從 \(0\) 數起),共 \(k - x - y\) 個。照位置去掉,同分的成績只會去掉一個:範例 1 的第 \(3\) 位有兩個 \(100\),只去掉其中一個。\(k \ge 3\) 而 \(x + y \le 2\),至少剩一個,不會除以 \(0\)。
- 除以剩下的個數 \(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\) 筆。