题目描述
编程能力测试(PAT)由浙江大学计算机科学与技术学院组织。
每次测试都会在多个地区同时进行,测试完成后,将会对成绩进行统计与合并,生成总排名。
你的任务就是编写一个程序,将各地区人员的成绩合并汇总,生成最终排名。
输入格式
第一行包含整数 N,表示测试将会在 N 个地区同时进行。
接下来是 N 个地区的成绩列表。
每个地区的成绩列表,第一行包含整数 K,表示该地区的测试人数。
接下来 K 行,每行包含一个学生的考号(13 位数字)以及该学生的成绩。
输出格式
第一行输出总考生人数。
然后用以下格式输出最终成绩排名列表:
registration_number final_rank location_number local_rank
也就是输出考号,最终排名,地区编号,地区排名。
地区编号按输入顺序依次为 1∼N。
按照最终排名从前到后的顺序输出每个人的信息。
具有相同分数的人的排名也要相同,相同分数的人,考号较小的先输出。
数据范围
1≤N≤100,
1≤K≤300,
分数在 [0,100] 范围内。
样例
输入样例
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
输出样例
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
算法1
(暴力枚举) $O(nklog(nk))$
直接结构体排序,这里面需要注意的是
1:分数相同的人的排名是一样的,但是学号小的人先输出,可以排完顺序后处理一遍.
2:注意是从大到小排的还是从小到大排序的
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=30000+10;
int n;
int sumk;
typedef struct
{
string rn;//考号
int fr;//最终排名
int ln;//地区编号
int lr;//地区排名
int gra;//成绩
}stu;
bool cmp(stu a,stu b)
{
if(a.gra!=b.gra)return a.gra<b.gra;
else return a.rn>b.rn;
}
stu s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;//每一个区域的人数
for(int j=sumk;j<sumk+k;j++)
{
cin>>s[j].rn>>s[j].gra;
s[j].ln=i;
}
sort(s+sumk,s+sumk+k,cmp);//排序计算区域排名
for(int j=sumk;j<sumk+k;j++)
{
s[j].lr=sumk+k-j;
}
for(int j=sumk+k-2;j>=sumk;j--)
{
if(s[j].gra==s[j+1].gra)s[j].lr=s[j+1].lr;
}
sumk+=k;
}
sort(s,s+sumk,cmp);
for(int i=0;i<sumk;i++)
{
s[i].fr=sumk-i;
}
for(int i=sumk-2;i>=0;i--)
{
if(s[i].gra==s[i+1].gra)s[i].fr=s[i+1].fr;
}
cout<<sumk<<endl;
for(int i=sumk-1;i>=0;i--)
{
cout<<s[i].rn<<" "<<s[i].fr<<" "<<s[i].ln<<" "<<s[i].lr<<endl;
}
return 0;
}