一、题目
The ranklist of PAT is generated from the status list, which shows the scores of the submissions. This time you are supposed to generate the ranklist for PAT.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive integers, N (≤), the total number of users, K (≤), the total number of problems, and M (≤), the total number of submissions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submission in the following format:
user_id problem_id partial_score_obtained
where partial_score_obtained is either − if the submission cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.
Output Specification:
For each test case, you are supposed to output the ranklist in the following format:
rank user_id total_score s[1] ... s[K]
where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-” must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.
The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.
二、题意理解
1、输入
(1)第一行是三个正整数N,K,M，分别代表用户的总人数，待求解问题的个数，用户提交答案的总次数。
(2)第二行是K个问题的满分数额。
(2)接下来的M行分别是某用户某一次的提交情况，格式为用户id 问题id 本次提交获得的分数。
注意：如果用户提交的答案不能通过编译，则所获分数是-1，一旦通过编译，分数区间为[0,满分]。
2、输出
需要对以下数据进行统计：
(1)对于曾被回答过的问题，统计最高得分。未回答过的问题不统计。
(2)将(1)中的最高得分进行累加，得到用户答题总分。
(3)统计用户回答满分的题目的个数。
注意：如果对于某道题，用户提交过答案但未通过编译，则录入分数是0而非-1。
按以下优先次序对用户的答题情况进行排序：
(1)先按总分降序排列。
(2)若总分相等，则按回答满分的题目个数降序排列。
(3)若(2)中都相等，则按用户id升序排列。
注意：如果某个用户“没有答案通过编译”，则不输出他的答题情况。这里“没有答案通过编译”包括了两种情况①用户回答了所有的问题，但所有答案都未通过编译；②用户仅回答了部分问题，但回答过的问题中答案都未通过编译。
三、算法思想
1、用户答题情况的结构体包含：
①答题总分；②每道题的得分；③回答满分的题目个数。
2、初始化结构体
①②初始化为0，③初始化为-2(-2表示未曾回答过，-1表示未通过编译)
3、读取数据时，边录入提交情况边统计每道题的最高得分
4、统计数据
两层循环，第一层——用户，第二层——题目，题目分数不小于0才计入总分中，如果所有题目分数均小于0，则表明用户“没有答案通过编译”，因此将其总分标记为-1,表示其答题情况不应该被输出。
5、排序
依照题意理解中的优先次序，排序算法本人采用希尔-表排序
6、输出结果
用类似于%05d控制用户id的格式，在输出用户每道题的分数时，若题目未曾被回答过，则输出-，若题目曾被回答但答案未通过编译则输出0，其余情况按实际得分输出。循环输出时若碰到用户总分为-1，则可直接结束循环。
注意：若用户总分相同，则并列排名。
四、C代码实现
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct{//用户答题情况
int eachpro[6];
int total;
int perfect;
}Score;
int N,K,M;
int fullmark[6];//每道题的满分数额
void Read(Score *sro)
{
int i,j,id,num,mark,flag;
for(i=0;i<N;++i){
for(j=1;j<=K;++j)
sro[i].eachpro[j]=-2;//-2表示未曾回答过，-1表示未通过编译
sro[i].total=0;
sro[i].perfect=0;
}
for(i=0;i<M;++i){
scanf("%d %d %d",&id,&num,&mark);
if(sro[id-1].eachpro[num]<mark)//边录入提交情况边统计最高得分
sro[id-1].eachpro[num]=mark;
}
for(i=0;i<N;++i){
flag=1;
for(j=1;j<=K;++j){
if(sro[i].eachpro[j]>=0){//题目得分不小于0才计入总分
flag=0;
sro[i].total+=sro[i].eachpro[j];
if(sro[i].eachpro[j]==fullmark[j])//统计回答满分的题目个数
sro[i].perfect++;
}
}
if(flag)//判定用户是否“没有答案通过编译”
sro[i].total=-1;
}
}
int Compare(Score *sro,int a,int b)//排序依据a>b?
{
if(sro[a].total>sro[b].total)//先按总分，降序
return 1;
else if(sro[a].total<sro[b].total)
return 0;
else{//按回答满分的题目个数，降序
if(sro[a].perfect>sro[b].perfect)
return 1;
else if(sro[a].perfect<sro[b].perfect)
return 0;
else{//按用户id，升序
if(a<b)
return 1;
else
return 0;
}
}
}
void ShellSort(Score *sro,int *index)//希尔-表排序，index存放的是结构体指针，也是用户id
{
int i,j,k,d,t;
for(k=log10(N+1)/log10(2);k>0;--k){
d=pow(2,k)-1;
for(i=d;i<N;++i){
t=index[i];
for(j=i;j>=d&&Compare(sro,t,index[j-d]);j-=d)
index[j]=index[j-d];
index[j]=t;
}
}
}
int main()
{
scanf("%d %d %d",&N,&K,&M);
int i;
for(i=1;i<=K;++i)
scanf("%d",&fullmark[i]);
Score* sro=(Score*)malloc(N*sizeof(Score));
Read(sro);
int* index=(int*)malloc(N*sizeof(int));
for(i=0;i<N;++i)
index[i]=i;
ShellSort(sro,index);
int cur,j;
for(i=0;i<N;++i){//输出结果
if(sro[index[i]].total==-1)
break;
if(!i||(i>0&&sro[index[i]].total!=sro[index[i-1]].total)){//与前一用户的总分不同，则按实际排名输出
printf("%d ",i+1);
cur=i+1;//最新用户排名
}else
printf("%d ",cur);//与前一用户总分相同，则按前一用户的排名输出
printf("%05d ",index[i]+1);
printf("%d ",sro[index[i]].total);
for(j=1;j<=K;++j){
if(sro[index[i]].eachpro[j]==-2)//未被回答过
printf("-");
else if(sro[index[i]].eachpro[j]==-1)//未通过编译
printf("0");
else
printf("%d",sro[index[i]].eachpro[j]);
if(j!=K)
printf(" ");
else
printf("\n");
}
}
return 0;
}