標題:
2022 C-競程比賽
[打印本頁]
作者:
may
時間:
2025-3-26 11:41
標題:
2022 C-競程比賽
C-競程比賽
時間限制 1 秒 / 記憶體限制 1 G
某大學終於要舉辦競程邀請賽了。
比賽規則是先用得到的分數來排名，得分較多者勝，若有兩隊得分相同，則使用解題時間來決定名次，解題時間越少，排名越前面
在經歷過數小的廝殺後，裁判們七嘴八舌地討論各隊究竟拿到第幾名。
由於太多裁判了，所以導致吵成一團，造成裁判長深感困擾。
因此裁判長希望有個系統可以快速地知道某一個名次是哪一隊。
● 輸入說明
第一行輸入兩個整數N和Q代表總共有N個隊伍，以及總共有Q個詢問。
接下來有N行，每行皆有兩個整數Xi，Ti以及一個字串Si。
分別代表第i個隊伍的得分，該隊伍解題縮花費的時間(秒)，以及該隊伍的名稱。
接下來有Q行，每行有一個整數
代表裁判想要知道排名第Ki的隊伍是哪一個。
[attach]20826[/attach]
隊伍名稱指包含英文字母
不會有兩個隊伍得分和解題時間皆相同
● 輸出說明
對於每一筆詢問，請輸出獲得該名次的隊伍名稱。
範例輸入1
3 3
10 60 AAA
30 60 BBB
20 60 CCC
1
2
3
範例輸出1
BBB
CCC
AAA
範例輸入2
5 3
50 60 AAA
50 50 BBB
30 10 CCC
10 40 DDD
20 30 EEE
1
2
3
範例輸出2
BBB
AAA
CCC
作者:
may
時間:
2025-3-26 11:53
回復
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
這些測試資料涵蓋 不同情境，確保程式邏輯正確，包括：
基本測試
相同得分但不同解題時間
所有得分皆不同
邊界值（最大最小得分與時間）
只有一個隊伍的情況
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
