成績指標 (APCS 2016-03 初級) 題解

Editorial for 成績指標 (APCS 2016-03 初級)

簡潔題意

讀入 \(n\) 個分數（\(1 \le n \le 20\)、每個介於 \(0\) 到 \(100\)），輸出三行：第一行把所有分數由小而大印出（空白間隔、行末無空白）；第二行印最高的不及格分數（\(< 60\)），全班及格就印 best case；第三行印最低的及格分數（\(\ge 60\)），全班不及格就印 worst case。（APCS 逐筆給分。）

排 \(n\) 個數：把「排三個」的招式推廣

只有三個數的時候，3.9 教過用三次「比較＋交換」就能排好；但這題人數不固定（最多 \(20\) 個），寫死幾次比較行不通了。招式可以推廣：由左到右檢查每一對相鄰的數，左邊比右邊大就交換——這樣掃完一輪，最大的數會一路被換到最右邊「就定位」；對剩下的再掃一輪，第二大的也就定位……重複 \(n - 1\) 輪，全部排好。

這個做法有名字，叫泡沫排序法（最大值像泡泡一樣浮上來）。它收在語法書下冊的 11.10，不過你會發現它用到的全是上冊的東西——陣列、雙層迴圈、比較與交換。它就是「排序三個整數」的延伸概念，學完上冊的你，是有機會在考場上自己把它想出來的：

// 泡沫排序：共 n - 1 輪；第 i 輪結束後，右邊 i 個位置已就定位
for (int i = 1; i < n; i++) {
    for (int j = 1; j <= n - i; j++) {
        if (s[j] > s[j + 1]) {         // 左邊比右邊大：順序錯了
            swap(s[j], s[j + 1]);      // 交換這對鄰居
        }
    }
}

交換用上冊 7.6 的 swap（記得 #include <algorithm>；當然也可以照 3.9 用暫存變數三行自己換）。內層上界 n - i 的意思是「已經就定位的最後 \(i\) 格不用再看」——其實這題 \(n \le 20\)，就算每輪都掃到底也才 \(20 \times 20 = 400\) 次比較，速度完全不是問題。

直接用 sort 也可以：如果你已經學到下冊的 11.4，整段泡沫排序可以換成一行——

sort(s + 1, s + n + 1);   // 1-base 陣列：左閉右開，兩端都要 + 1

sort 跟 swap 住在同一個標頭檔 <algorithm>，所以連 #include 都不用動，其餘程式完全不變。考場上會什麼就用什麼，兩條路都是滿分。

排好之後：答案就在及格線的交界

分數由小到大排好，不及格的（\(< 60\)）全擠在左邊、及格的（\(\ge 60\)）全在右邊，題目要的兩個指標就是交界處的兩個數：「最高不及格」是最後一個 \(< 60\) 的、「最低及格」是第一個 \(\ge 60\) 的。由小到大掃一遍就拿得到：遇到 \(< 60\) 就更新 highFail（越後面越大，最後留下的就是最高不及格）；遇到第一個 \(\ge 60\) 的把它記進 lowPass，之後不再動。

「還沒找到」用什麼表示？不能用 \(0\)——\(0\) 是合法的分數（範例 1 就有人考 \(0\) 分）。分數保證不是負的，所以拿 \(-1\) 當「還沒找到」的記號最安全：掃完之後 highFail 還是 \(-1\)，代表全班沒有任何不及格，第二行印 best case；lowPass 還是 \(-1\) 代表全班沒人及格，第三行印 worst case。

第一行的輸出格式「行末無空白」，用「數字之間才放空白」的寫法：第一個數字前不印，之後每個數字前補一個空白。完整程式：

#include <iostream>
#include <algorithm>   // swap 住在這（上冊 7.6）
using namespace std;

const int MAX_N = 25;  // 人數最多 20，開一點餘裕
int s[MAX_N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }

    // 泡沫排序：共 n - 1 輪；第 i 輪結束後，右邊 i 個位置已就定位
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (s[j] > s[j + 1]) {         // 左邊比右邊大：順序錯了
                swap(s[j], s[j + 1]);      // 交換這對鄰居
            }
        }
    }

    // 第一行：由小到大，「數字之間」才放空白
    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << " ";
        }
        cout << s[i];
    }
    cout << endl;

    // 由小到大掃一遍：「最高不及格」不斷更新、「最低及格」只記第一個
    int highFail = -1;   // -1 代表「還沒找到」：分數最小是 0，-1 不可能是真分數
    int lowPass = -1;
    for (int i = 1; i <= n; i++) {
        if (s[i] < 60) {
            highFail = s[i];               // 越後面越大，最後留下的就是最高不及格
        }
        if (s[i] >= 60 && lowPass == -1) {
            lowPass = s[i];                // 由小到大，第一個及格的就是最低及格
        }
    }

    if (highFail == -1) {
        cout << "best case" << endl;       // 沒有任何不及格：全班及格
    } else {
        cout << highFail << endl;
    }
    if (lowPass == -1) {
        cout << "worst case" << endl;      // 沒有任何及格：全班不及格
    } else {
        cout << lowPass << endl;
    }
    return 0;
}

測過再交：把及格線和 \(0\) 分踩一遍

三個範例已經涵蓋「兩個指標都有」「全班不及格（worst case）」「全班及格（best case）」三種局面，但有兩個地雷範例沒踩到：恰好 \(60\) 分（及格線本人，\(\ge 60\) 算及格）和有人考 \(0\) 分時你的「還沒找到」記號會不會被搞混。自己補幾筆：

輸入	第一行	第二行	第三行	這一筆在測什麼
`2` ／ `59 60`	`59 60`	`59`	`60`	及格線兩側貼著站：\(60\) 要算及格
`3` ／ `60 60 60`	`60 60 60`	`best case`	`60`	全班恰好 \(60\)：及格線寫 `> 60` 的話兩行全錯
`3` ／ `0 100 100`	`0 100 100`	`0`	`100`	\(0\) 分是合法分數：拿 \(0\) 當「還沒找到」會誤印 `best case`
`3` ／ `100 90 80`	`80 90 100`	`best case`	`80`	遞減輸入：驗排序真的有排

四筆都親眼看過正確，這題就穩了。

常犯錯誤

及格線的等號：及格是 \(\ge 60\)，恰好 \(60\) 分算及格。條件寫成 > 60 的話，60 60 60 這筆第二行會印 60、第三行印 worst case——兩行全錯。
best case／worst case 對應搞反：best case 印在第二行（找不到不及格＝全班及格＝好事），worst case 在第三行。範例 2、3 剛好一人示範一種，貼反的話兩個範例當場全掛。
拿 \(0\) 當「還沒找到」的記號：\(0\) 是合法分數（範例 1 就有人考 \(0\) 分）。0 100 100 這筆，「最高不及格」明明是 \(0\)，卻會因為 highFail == 0 被誤判成「沒找到」而印出 best case。用 \(-1\)（分數不可能是負的），或另外開一個 bool 旗標記「找到了沒」。
第二、三行順序顛倒：先印最高不及格、再印最低及格——跟直覺的「先報好消息」相反。範例 1 就抓得到（印成 66 55 就是反了）。
泡沫排序內層越界：內層要保證 s[j + 1] 摸得到——上界寫成 j <= n 就會讀到 s[n + 1]，這是越界的未定義行為（6.8），常常「看起來沒事」、換個環境就翻車。照課本寫 j <= n - i（或至少 j <= n - 1）。
第一行行末多印空白：用「數字之間才放空白」的寫法（if (i > 1) cout << " ";）。本站的評測其實對行末空白寬容，但題目明寫行末無空白，而檢定現場的評測嚴不嚴格沒人跟你保證。