回復 1# may - #include <bits/stdc++.h>
- //#include <iostream>
- //#include <vector>
- //#include <algorithm>
- using namespace std;
- struct Team {
- int score, time;
- string name;
- };
- // 排序規則：
- // 1. 依據 score 由大到小排序
- // 2. 若 score 相同，則依據 time 由小到大排序
- bool compareTeams(const Team &a, const Team &b) {
- if (a.score != b.score)
- return a.score > b.score; // 分數高者優先
- return a.time < b.time; // 若分數相同，時間少者優先
- }
- int main() {
- int N, Q;
- cin >> N >> Q;
- vector<Team> teams(N);
- // 讀取隊伍資料
- for (int i = 0; i < N; i++) {
- cin >> teams[i].score >> teams[i].time >> teams[i].name;
- }
- // 依據題目規則排序
- sort(teams.begin(), teams.end(), compareTeams);
- // 讀取查詢並輸出結果
- for (int i = 0; i < Q; i++) {
- int rank;
- cin >> rank;
- cout << teams[rank - 1].name << endl; // rank 是從 1 開始的，因此索引需減 1
- }
- 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
這些測試資料涵蓋 不同情境，確保程式邏輯正確，包括：
基本測試
相同得分但不同解題時間
所有得分皆不同
邊界值（最大最小得分與時間）
只有一個隊伍的情況 |
