Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive number N (≤100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (≤300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.
Output Specification:
For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:
registration_number final_rank location_number local_rank
The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.
Sample Input:
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
Sample Output:
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4題意：
有n個考場，每個考場有若干考生，
現給出各個考場所有考生的準考證號與分數，要求按分數從高到低分別進行①單考場內排序②總排序，
最終輸出參加考試的考生數以及每個考生的①準考證號②總排名③考場號④考場內排名
思路：
1、排序的邏輯
①按分數從高到低排序
②分數相同時，按準考證號從小到大排序
2、所需要的資訊及資訊的存盤
①對于單個學生student，需要對應的準考證號id，分數score，考場號location_number，考場內排名local_rank，總排名sum_rank——結構體Student，并創建一個足夠大的結構體陣列
②此外還需要總考場數n，總考生數num，單個考場內的考生數k——int型變數
3、排序邏輯的實作
1 bool cmp(Student a, Student b) { 2 if (a.score != b.score) { 3 return a.score > b.score; 4 } else { 5 return strcmp(a.id, b.id) < 0; 6 } 7 }
4、main() 分步分析
主要分為兩個部分：
（1）給單個考場內的考生排名
①有n個考場，因此最外層要有for回圈從1到n遍歷每個考場
1 for (int i = 1; i <= n; i++) { 2 }
②每個考場內有k個學生，因此內層要有for回圈從0到k-1遍歷每個學生
1 for (int j = 0; j < k; j++) { 2 }
③接收輸入的準考證號id與分數score，按順序存入結構體陣列中
1 scanf("%s %d", stu[num].id, &stu[num].score);
④當前考場的學生遍歷完后，呼叫排序函式sort()對當前考場內的所有考生按排序邏輯進行排序
1 sort(stu, stu + k, cmp);
⑤按④的排序結果，依次給每個考生的考場內排名local_rank賦值
1 stu[0].local_rank = 1; //第一個考生的排名為1 2 for (int j = 1; j < k; j++) { 3 if (stu[j].score == stu[j - 1].score) { 4 stu[j].local_rank = stu[j - 1].local_rank; //分數相同則排名相同 5 } else { 6 stu[j].local_rank = j + 1; //分數不同則+1 7 } 8 }
（2）給所有的考生排名
⑥呼叫排序函式sort()對所有考生按排序邏輯進行排序（代碼同④）
⑦按⑥的排序結果，依次給每個考生的總排名sum_rank賦值（代碼同⑤）
5、踩到了第一個坑
只開一個Student型別的陣列，但是要存放多個考場的考生資訊，因此遍歷和排序時不能簡單的從下標0開始
解決：
引入新變數 總考生數num
于是可知，每次接收完一個新考場的考生資料時，此考場考生對應的下標范圍是num - k ~ num
6、main() 雛形
1 scanf("%d", &n); //考場數 2 for (int i = 1; i <= n; i++) { //考場號，要從1開始 3 scanf("%d", &k); //當前考場人數 4 5 /*錄入資料*/ 6 for (int j = 0; j < k; j++) { 7 scanf("%s %d", stu[num].id, &stu[num].score); 8 stu[num].location_number = i; 9 num++; //通過這個計算總考生數 10 } 11 12 /*對剛錄入的這個考場考生進行排序并賦名次*/ 13 sort(stu + num - k, stu + num, cmp); 14 stu[num - k].local_rank = 1; 15 for (int j = num - k + 1; j < num; j++) { 16 if (stu[j].score == stu[j - 1].score) { 17 stu[j].local_rank = stu[j - 1].local_rank; 18 } else { 19 stu[j].local_rank = j + 1 - (num - k);//j為此考生之前的人數，- （num - k）為去掉前面其他考場的人數，+ 1后即得到此考生在本考場的排名 20 } 21 } 22 23 } 24 25 /*對所有考生進行排序并賦名次*/ 26 sort(stu, stu + num, cmp); 27 stu[0].sum_rank = 1; 28 for (int i = 1; i < num; i++) { 29 if (stu[i].score == stu[i - 1].score) { 30 stu[i].sum_rank = stu[i - 1].sum_rank; 31 } else { 32 stu[i].sum_rank = i + 1; 33 } 34 } 35
7、優化
總排名sum_rank是在整個程式的最后才得到的
它之后緊跟著的就是要將sum_rank輸出——額外去存盤的意義不大
并且sum_rank的值只有兩種情況①和前一個相同②i + 1——值的計算簡單，沒有其他的相關項
所以考慮將“計算出總排名→存入sum_rank→輸出stu[i].sum_rank”簡化為“計算出總排名→輸出總排名”
1 sort(stu, stu + num, cmp); 2 int r = 1; //r即為總排名，初始為1 3 for (int i = 0; i < num; i++) { 4 //i > 0:從第二個考生開始（stu[0]為第一個考生） 5 //stu[i].score != stu[i - 1].score: 6 //若兩人分數相同，則總排名r相同； 7 //若不同，則后一個人的排名為其前面的人數 i + 1； 8 if (i > 0 && stu[i].score != stu[i - 1].score) { 9 r = i + 1; 10 } 11 }
8、main() 最終形態
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 struct Student { 6 char id[15]; 7 int score; 8 int location_number; 9 int local_rank; 10 int sum_rank; //test 11 }stu[30010]; 12 bool cmp(Student a, Student b) { 13 if (a.score != b.score) { 14 return a.score > b.score; 15 } else { 16 return strcmp(a.id, b.id) < 0; 17 } 18 } 19 int main() { 20 int n, k, num = 0; 21 scanf("%d", &n); 22 for (int i = 1; i <= n; i++) { 23 scanf("%d", &k); 24 for (int j = 0; j < k; j++) { 25 scanf("%s %d", stu[num].id, &stu[num].score); 26 stu[num].location_number = i; 27 num++; 28 } 29 sort(stu + num - k, stu + num, cmp); 30 stu[num - k].local_rank = 1; 31 for (int j = num - k + 1; j < num; j++) { 32 if (stu[j].score == stu[j - 1].score) { 33 stu[j].local_rank = stu[j - 1].local_rank; 34 } else { 35 stu[j].local_rank = j + 1 - (num - k); 36 } 37 } 38 } 39 printf("%d\n", num); 40 sort(stu, stu + num, cmp); 41 int r = 1; 42 for (int i = 0; i < num; i++) { 43 if (i > 0 && stu[i].score != stu[i - 1].score) { 44 r = i + 1; 45 } 46 printf("%s ", stu[i].id); 47 printf("%d %d %d\n", r, stu[i].location_number, stu[i].local_rank); 48 } 49 return 0; 50 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102326.html
標籤：其他
上一篇：Trie樹模板