1012 The Best Rank (25 分)
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), and E - 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, E and A - 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.
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, M and E. Then there are M lines, each containing a student ID.
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.
思路分析
这种题用SQL写就是一行代码的事情，但是用C语言实现得考虑如何去存储数据，
如何去表示这种一一对应的关系。
由于数据量不是很大，可以直接用时间复杂度为O（n^2）的排序算法，不会超时
这种题不难，就是麻烦
#include<cstdio> #include<iostream> #define MAX 10000 #define NUL -1 typedef struct{ int id; int c;int crank; int m;int mrank; int e;int erank; int sum;int sumrank; }PERSON; PERSON stu[MAX]; int sumarr[MAX]={0};//存放的所有的sum的值 int summap[500]={0};//sum的成绩对应的排名 int carr[MAX]={0}; int cmap[500]={0}; int marr[MAX]={0}; int mmap[500]={0}; int earr[MAX]={0}; int emap[500]={0}; int idmap[1999999]={-1}; int main() { for(int i=0;i<1999999;i++) { idmap[i]=-1; } //输入部分 int n=0,m=0; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { scanf("%d %d %d %d",&stu[i].id,&stu[i].c,&stu[i].m,&stu[i].e); stu[i].sum = stu[i].c+stu[i].m+stu[i].e; sumarr[i]=stu[i].sum; carr[i]=stu[i].c; marr[i]=stu[i].m; earr[i]=stu[i].e; idmap[stu[i].id]=i;//id-map } //sumarr 存放所有sum值 从大到小 for(int j=0;j<n;j++) { int temp; for(int i=n-1;i>=0;i--) { if(sumarr[i]<sumarr[i+1]) { temp=sumarr[i]; sumarr[i]=sumarr[i+1]; sumarr[i+1] = temp; } if(carr[i]<carr[i+1]) { temp=carr[i]; carr[i]=carr[i+1]; carr[i+1] = temp; } if(marr[i]<marr[i+1]) { temp=marr[i]; marr[i]=marr[i+1]; marr[i+1] = temp; } if(earr[i]<earr[i+1]) { temp=earr[i]; earr[i]=earr[i+1]; earr[i+1] = temp; } } } //排序函数 for(int temp=1,rank=1, i=0;i<n;i++) { if(i==0)summap[sumarr[i]]=rank; else { if(sumarr[i]!=sumarr[i-1]) { rank = rank +temp; summap[sumarr[i]]=rank; temp = 1; } else { summap[sumarr[i]]=rank; temp++; } } } for(int temp=1,rank=1, i=0;i<n;i++) { if(i==0)cmap[carr[i]]=rank; else { if(carr[i]!=carr[i-1]) { rank = rank +temp; cmap[carr[i]]=rank; temp = 1; } else { cmap[carr[i]]=rank; temp++; } } } for(int temp=1,rank=1, i=0;i<n;i++) { if(i==0)mmap[marr[i]]=rank; else { if(marr[i]!=marr[i-1]) { rank = rank +temp; mmap[marr[i]]=rank; temp = 1; } else { mmap[marr[i]]=rank; temp++; } } } for(int temp=1,rank=1, i=0;i<n;i++) { if(i==0)emap[earr[i]]=rank; else { if(earr[i]!=earr[i-1]) { rank = rank +temp; emap[earr[i]]=rank; temp = 1; } else { emap[earr[i]]=rank; temp++; } } } //输出检测 for(int i=0;i<n;i++) { stu[i].sumrank = summap[stu[i].sum]; stu[i].crank = cmap[stu[i].c]; stu[i].mrank = mmap[stu[i].m]; stu[i].erank = emap[stu[i].e]; } for(int id=0,i=0;i<m;i++) { scanf("%d",&id); if(idmap[id]==-1)printf("N/A\n"); else if(idmap[id]!=-1) { int a=stu[idmap[id]].sumrank; int c=stu[idmap[id]].crank; int m=stu[idmap[id]].mrank; int e=stu[idmap[id]].erank; int arr[4]; arr[0]=a;arr[1]=c; arr[2]=m;arr[3]=e; int min = arr[0];//初始是a 然后找最小的 for(int jj=1;jj<4;jj++) { if(arr[jj]<min)min=arr[jj]; } if(min==a) { printf("%d A\n",min);continue; } if(min==c) { printf("%d C\n",min);continue; } if(min==m) { printf("%d M\n",min);continue; } if(min==e) { printf("%d E\n",min);continue; } } } }
