遊戲選角 題解|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,等於把沒人坐過的初值直接印給你看)。這四筆都親眼看過正確,這題就穩了。
常犯錯誤
-
忘記把原本的第一名退成第二名:第一名被換掉時只更新了
best/bestA/bestD,漏掉搬去第二名的那三行。範例 1 剛好躲得過去,範例 2 會印出6 6;自測表第 \(1\) 列會印出0 0(第二名的位置從頭到尾沒人坐過)。 -
退位時只搬了綜合能力:寫了
second = best;,卻漏了secondA = bestA;和secondD = bestD;,第二名的攻擊力、防禦力還是舊的。範例 1 照樣會過,範例 2 會印出0 0。 -
擂台的變數沒有初始化:
int best, bestA, bestD;就直接拿去比大小,-Wall當場警告;自己測「剛好是對的」跟「保證是對的」是兩回事。 -
綜合能力算成 \(a + d\):題目寫的是攻擊力與防禦力的平方和。範例 1 會印出
3 2、範例 2 會印出6 6。 -
印出第一名:印成
bestA/bestD。範例 1 會印出5 2、範例 2 會印出5 8。