回復 1# may - #include <bits/stdc++.h>
- using namespace std;
- struct team { //team 結構體儲存隊伍資訊：score（得分）time（解題時間）name（隊伍名稱）
- int score, time;
- string name;
- };
- bool cmp(team a, team b) { //定義排序函式 cmp
- if(a.score == b.score) return a.time < b.time; //排序規則：優先根據 score（得分）排序，分數高的排前面（遞減排序）。若 score 相同，則根據 time（解題時間）排序，時間少的排前面（遞增排序）。這個排序函式會被 sort() 使用，讓隊伍按照規定順序排列。
- return a.score > b.score;
- }
- int main(){
- int n, q; //n：隊伍數量,q：查詢數量。
- cin >> n >> q;
- vector<team> arr(n); //使用 vector<team> arr(n); 建立大小為 n 的 vector 來儲存隊伍資訊。
- for(int i = 0; i < n; i++) {
- cin >> arr[i].score >> arr[i].time >> arr[i].name;
- }
- sort(arr.begin(), arr.end(), cmp); //使用 sort() 函式，並傳入 cmp 作為比較函式，以 符合比賽規則的順序 來排列隊伍。
- for(int i = 0; i < q; i++) { //讀取 q 筆查詢，每筆輸入一個整數 n（代表排名 n 的隊伍）。輸出對應的隊伍名稱：由於 arr 是從索引 0 開始的，而排名 n 是從 1 開始，因此 arr[n-1].name 取得正確的隊伍名稱。
- cin >> n;
- cout << arr[n-1].name << endl;
- }
- return 0;
- }
程式解析
定義 Team 結構體
存放隊伍的 score（得分）、time（解題時間）和 name（名稱）。
compareTeams 排序函式
score 越大排名越前（a.score > b.score）。
若 score 相同，則 time 越小排名越前（a.time < b.time）。
讀取輸入
使用 vector<Team> 儲存 N 隊伍資訊。
排序
sort() 根據 compareTeams 進行排序。
處理查詢
讀取 Q 筆查詢，輸出對應名次的隊伍名稱。
由於 Ki 是從 1 開始 計數的，因此需要 rank - 1 來索引 vector。
時間複雜度分析
讀取輸入：O(N)
排序：O(N log N)
查詢：O(Q)
總時間複雜度：O(N log N + Q)
這對於 N 最大為 10^5 的情況是可行的。
------------------------------------------
測資:
測試資料 00：基本測試
輸入
3 3
10 60 AAA
30 60 BBB
20 60 CCC
1
2
3
預期輸出
BBB
CCC
AAA
測試資料01：相同得分但不同解題時間
輸入
5 3
50 60 AAA
50 50 BBB
30 10 CCC
10 40 DDD
20 30 EEE
1
2
3
預期輸出
BBB
AAA
CCC
測試資料 02：所有隊伍得分皆不同
輸入
4 4
100 20 A
90 30 B
80 25 C
70 40 D
1
2
3
4
預期輸出
A
B
C
D
測試資料 03：極端邊界測試（最低與最高得分）
輸入
6 2
1000 5 X
500 10 Y
500 8 Z
100 50 W
100 60 V
10 100 U
1
6
預期輸出
X
U
測試資料04：單一隊伍，單一查詢
輸入
1 1
999 1 WINNER
1
預期輸出
WINNER
這些測試資料涵蓋 不同情境，確保程式邏輯正確，包括：
基本測試
相同得分但不同解題時間
所有得分皆不同
邊界值（最大最小得分與時間）
只有一個隊伍的情況 |
