遊戲選角 題解|APCS 2024 年 1 月初級 第 1 題


簡潔題意

有 \(n\) 位角色,第 \(i\) 位的攻擊力是 \(a_i\)、防禦力是 \(d_i\),「綜合能力」定義成 \(a_i^2 + d_i^2\)。請找出綜合能力第二高的角色,輸出他的攻擊力與防禦力(\(3 \le n \le 20\),攻擊力與防禦力都是 \(1\) 到 \(100\) 的整數,題目保證所有角色的綜合能力兩兩相異)

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

  • 子題組 1(\(60\) 分):\(n = 3\)。
  • 子題組 2(\(40\) 分):無額外限制。

綜合能力:這題唯一要算的東西

題目說得很直白,綜合能力就是 \(a^2 + d^2\)。動手之前先確認兩件事。

第一,會不會溢位? 攻擊力與防禦力最大都是 \(100\),所以綜合能力最大是 \(100^2 + 100^2 = 20000\)——離 int 的上限(大約 \(2.1 \times 10^9\))遠得很,全程用 int 完全安全。這種估算的方法在上冊 2.9。

第二,\(0\) 可以拿來當「還沒有人」的記號。 攻擊力與防禦力最小都是 \(1\),所以綜合能力最小是 \(1^2 + 1^2 = 2\)——\(0\) 一定比任何角色都低,用它當初值很安全。(這個「初值要挑值域外的數」的判斷,等一下就派上用場。)

一邊讀、一邊只記住前兩名

上冊 3.12 的熱身教過「打擂台」找最大值:先讓第一個人上台當擂主,後面的人輪流來挑戰,誰大誰當新擂主。這題要的是第二名,所以擂台上留兩個位置:第一名和第二名。角色一位一位讀進來,每讀一位就上台比一次,前面的人比完就不用再記。

一位新角色走上台時,只有三種情況:

新角色的綜合能力 該做什麼
比第一名高 原本的第一名退成第二名,新角色當第一名
沒贏第一名,但比第二名高 直接取代第二名,第一名不動
連第二名都贏不了 什麼都不用做

第一種情況是這題的重點:第一名被換掉的時候,原本的第一名不是消失,而是退成第二名——到目前為止,他還是第二強的人。漏掉這件事,程式在很多情況下看起來還是對的(下面的自測表就是為了逼出它)。

擂台上總共只有兩個位置,每個位置要記三件事(綜合能力、攻擊力、防禦力),六個變數就裝得下:

  • best、bestA、bestD:目前第一名的綜合能力、攻擊力、防禦力
  • second、secondA、secondD:目前第二名的

初值一定要寫,而且要用前面說的 \(0\):擂台一開始沒有人,綜合能力要先放一個「比誰都低」的記號。每位角色的綜合能力至少是 \(2\),第一位上台的角色一定贏得了 \(0\)。變數宣告了卻沒給初值就拿去比大小,裡面裝的是什麼完全沒有保證(上冊 2.5 有整段在講這件事);開了 -Wall 的編譯器還會直接對你說 ‘best’ may be used uninitialized——編譯器都開口了就要處理,別賭它剛好是 \(0\)。

完整程式碼:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int best = 0, bestA = 0, bestD = 0;        // 目前第一名:綜合能力、攻擊力、防禦力
    int second = 0, secondA = 0, secondD = 0;  // 目前第二名
    for (int i = 1; i <= n; i++) {
        int a, d;
        cin >> a >> d;
        int s = a * a + d * d;       // 這位角色的綜合能力
        if (s > best) {              // 新的第一名:原本的第一名退成第二名
            second = best;
            secondA = bestA;
            secondD = bestD;
            best = s;
            bestA = a;
            bestD = d;
        } else if (s > second) {     // 沒贏第一名,但贏過第二名
            second = s;
            secondA = a;
            secondD = d;
        }
    }
    cout << secondA << " " << secondD << endl;
    return 0;
}

退位那幾行有順序:一定要先把第一名搬去第二名,再讓新角色坐上第一名。順序反過來寫(先 best = s; 再 second = best;),搬過去的就變成新角色自己,第一名和第二名會一模一樣。

第二個分支要寫 else if 不能寫 if:一位角色只佔一個位置,剛當上第一名的人不該再被拿去跟第二名比一次——寫成 if,他會馬上連第二名的位置也佔走。

題目保證 \(n \ge 3\),至少三個人上過台,第二名的位置一定坐得滿;也保證綜合能力兩兩相異,所以「第二高」不會有兩個人來搶。

測過再交:兩個範例的第一名都在第 \(2\) 筆

先盤點範例蓋到了什麼:範例 1 的第一名在第 \(2\) 筆、第二名在第 \(3\) 筆;範例 2 的第一名在第 \(2\) 筆、第二名在第 \(1\) 筆。「第一名在最後一筆才出現」和「第一名第一筆就定案」兩種局面,範例都沒測到。

自己補這幾筆再交:

想測什麼 輸入 正確輸出
第一名最後一筆才出現(原本的第一名要退成第二名) 3 / 1 1 / 2 2 / 3 3 2 2
第一名第一筆就定案(後面的人只能爭第二) 3 / 5 5 / 3 3 / 1 1 3 3
值域兩端:最小的 1 1 與最大的 100 100 3 / 100 100 / 1 1 / 3 4 3 4
\(n\) 到上限 \(20\) 20 之後接 1 1、2 1、……、20 1 19 1

第一列會把「忘記把原本的第一名退成第二名」當場抓出來(那種寫法在這筆會印出 0 0,等於把沒人坐過的初值直接印給你看)。這四筆都親眼看過正確,這題就穩了。

常犯錯誤
  1. 忘記把原本的第一名退成第二名:第一名被換掉時只更新了 best/bestA/bestD,漏掉搬去第二名的那三行。範例 1 剛好躲得過去,範例 2 會印出 6 6;自測表第 \(1\) 列會印出 0 0(第二名的位置從頭到尾沒人坐過)。

  2. 退位時只搬了綜合能力:寫了 second = best;,卻漏了 secondA = bestA; 和 secondD = bestD;,第二名的攻擊力、防禦力還是舊的。範例 1 照樣會過,範例 2 會印出 0 0。

  3. 擂台的變數沒有初始化:int best, bestA, bestD; 就直接拿去比大小,-Wall 當場警告;自己測「剛好是對的」跟「保證是對的」是兩回事。

  4. 綜合能力算成 \(a + d\):題目寫的是攻擊力與防禦力的平方和。範例 1 會印出 3 2、範例 2 會印出 6 6。

  5. 印出第一名:印成 bestA/bestD。範例 1 會印出 5 2、範例 2 會印出 5 8。