PAT 甲级 1025
参考自:https://blog.****.net/richenyunqi/article/details/79307686
题目描述
输入:第一行输入N,表示考场的总数量(the number of test locations)
第二行输入K,考试学生的数量(the number of testees)
接下来K行是这些学生的信息,包括考号、分数,它们用空格分开
输出:第一行,总考生数量
接下来几行,每行包括考号、最终排名、考场号、考场排名
算法设计
需要计算考生在考场中的排名,在所有考生中的排名。
每读入一个考场的考生的信息,就进行排名,每一个考场内的排名计算完毕后再计算总排名。
C++代码
#include<bits/stdc++.h>
using namespace std;
//结构体,包含每个考生的多个数据
struct Testee{ //考生类
long long id; //考生编号有13位,long 10位放不下
int score,localNumber,rank[2]={1,1}; //分数、考场号、考场排名、总排名
};
vector<Testee>testee; //存储考生的vector,testtee是向量名
//cmp = 排序规则
bool cmp(const Testee&t1,const Testee&t2){ //比较函数,先按成绩由大到小排序,成绩相同的按准考证号由小到大排序
if(t1.score!=t2.score)
return t1.score>t2.score;
else
return t1.id<t2.id;
}
//完成向量连续多个元素的排序任务,根据index的不同排序的内容不同,0 = 考场内排名,1 = 总排名
void setRank(int index,int _begin,int _end){ //计算排名,index为0、1分别代表计算考场内排名、总排名
sort(testee.begin()+_begin,testee.begin()+_end,cmp); //成绩由大到小排序
for(int j=_begin+1;j<testee.size();++j) //计算排名
if(testee[j].score==testee[j-1].score) //等于前一个,排名也一样
testee[j].rank[index]=testee[j-1].rank[index];
else //排名+1
testee[j].rank[index]=j-_begin+1;
}
int main(){
int N,K;
scanf("%d",&N);
for(int i=1;i<=N;++i){ //i代表考场号,由1~N编号
scanf("%d",&K); //读入整个考场人数
int start=testee.size(); //每次循环得到testee中需要排序的首个元素的索引,比如:i=1表示1号考场,考生人数为k1,testee需要排序的部分索引是0~k1-1,一共k1个元素,i=2时,testee需要排序的部分索引是k1~k2+k2-1
for(int j=0;j<K;++j){ //循环K次,读入考生信息
Testee t;
scanf("%lld%d",&t.id,&t.score);
t.localNumber=i; //储存考场号
testee.push_back(t); //将刚才的关于考生的信息储存起来
}
setRank(0,start,start+K);
}
setRank(1,0,testee.size());
printf("%d\n",testee.size()); //输出考生总人数
for(int i=0;i<testee.size();++i)
printf("%013lld %d %d %d\n",testee[i].id,testee[i].rank[1],testee[i].localNumber,testee[i].rank[0]);
return 0;
}