PAT——甲級1012：The Best Rank（有坑）
1012 The Best Rank （25 point(s)）
To evaluate the performance of our first year CS majored students, we consider their grades of three courses only:
C- C Programming Language,M- Mathematics (Calculus or Linear Algrbra), andE- English. At the mean time, we encourage students by emphasizing on their best ranks -- that is, among the four ranks with respect to the three courses and the average grade, we print the best rank for each student.For example, The grades of
C,M,EandA- Average of 4 students are given as the following:StudentID C M E A 310101 98 85 88 90 310102 70 95 88 84 310103 82 87 94 88 310104 91 91 91 91Then the best ranks for all the students are No.1 since the 1st one has done the best in C Programming Language, while the 2nd one in Mathematics, the 3rd one in English, and the last one in average.
Input Specification:
Each input file contains one test case. Each case starts with a line containing 2 numbers N and M (≤2000), which are the total number of students, and the number of students who would check their ranks, respectively. Then N lines follow, each contains a student ID which is a string of 6 digits, followed by the three integer grades (in the range of [0, 100]) of that student in the order of
C,MandE. Then there are M lines, each containing a student ID.Output Specification:
For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.
The priorities of the ranking methods are ordered as
A>C>M>E. Hence if there are two or more ways for a student to obtain the same best rank, output the one with the highest priority.If a student is not on the grading list, simply output
N/A.Sample Input:
5 6 310101 98 85 88 310102 70 95 88 310103 82 87 94 310104 91 91 91 310105 85 90 90 310101 310102 310103 310104 310105 999999Sample Output:
1 C 1 M 1 E 1 A 3 A N/A
這個題倒是不難，但是挺復雜的。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct Student { char id[6]; int A, C, M, E;//每個同學的分數 int A_rank, C_rank, M_rank, E_rank;//每個分數的排名 }stu[100010]; bool cmp_A(Student a, Student b) { return a.A > b.A; }//這四個函數是排序的時候用的，分別對四個成績排序。 bool cmp_C(Student a, Student b) { return a.C > b.C; } bool cmp_M(Student a, Student b) { return a.M > b.M; } bool cmp_E(Student a, Student b) { return a.E > b.E; } void print_max(int a, int c, int m, int e) {//這個函數打印出來最高排名。a c m e 分別代表的是各成績排名。 if (a <= c && a <= m && a <= e)printf("%d A\n", a);//注意這里的=，符合優先級A>C>M>E else if (c < a&&c <= m && c <= e)printf("%d C\n", c); else if (m < a&&m < c && m <= e)printf("%d M\n", m); else printf("%d E\n", e); } int main() { int m, n; scanf("%d%d", &n, &m); for (int i = 0;i < n;i++) { scanf("%s%d%d%d", stu[i].id, &stu[i].C,&stu[i].M,&stu[i].E); stu[i].A = (stu[i].C+stu[i].M + stu[i].E) / 3; } sort(stu, stu + n, cmp_A);//對A成績排序 stu[0].A_rank = 1; for (int i = 1;i < n;i++) { //對A成績排名 if (stu[i].A == stu[i - 1].A) stu[i].A_rank = stu[i - 1].A_rank; else stu[i].A_rank = i + 1; } //對C成績排序，排名 sort(stu, stu + n, cmp_C); stu[0].C_rank = 1; for (int i = 1;i < n;i++) { if (stu[i].C == stu[i - 1].C) stu[i].C_rank = stu[i - 1].C_rank; else stu[i].C_rank = i + 1; } //對M成績排序，排名 sort(stu, stu + n, cmp_M); for (int i = 0;i < n;i++) stu[i].M_rank = i + 1; stu[0].M_rank = 1; for (int i = 1;i < n;i++) { if (stu[i].M == stu[i - 1].M) stu[i].M_rank = stu[i - 1].M_rank; else stu[i].M_rank = i + 1; } //對E成績排序，排名 sort(stu, stu + n, cmp_E); for (int i = 0;i < n;i++) stu[i].E_rank = i + 1; stu[0].E_rank = 1; for (int i = 1;i < n;i++) { if (stu[i].E == stu[i - 1].E) stu[i].E_rank = stu[i - 1].E_rank; else stu[i].E_rank = i + 1; } for (int i=0;i < m;i++) { char M_ID[6]; bool flag = false; scanf("%s", M_ID); for (int j = 0; j < n; j++) { if (strcmp(M_ID, stu[j].id) == 0){//尋找這個同學的信息。 print_max(stu[j].A_rank, stu[j].C_rank, stu[j].M_rank, stu[j].E_rank); flag = true; break; } } if (!flag) printf("N/A\n"); } return 0; }
我這個可以改進一下，把id當int儲存，題目中說了是6位數字。
并且后面處理查找ID的時候，復雜度比較高，算法筆記里面是申請了rank[10000000][4]這么大的數組。儲存學生的排名信息，直接用ID去訪問。但我總覺得申請這么大的內存，好虛呀，犧牲空間換時間。
其他我們的思路差不多。先儲存，再分別排序，再對排序結果選擇最高的輸出。
這道題有個坑！
題目里面也沒說，就是相同分數是怎么算排名。
比如91,90,88,88,84應該算作1,2,3,3,5。切記不要算作1,2,3,3,4。
浙公網安備 33010602011771號