PAT 甲级1025 PAT Ranking (25 分)(结构体排序,第一次超时了,一次sort即可小技巧优化)
2024-09-03 18:57:29
题意:
给定一次PAT测试的成绩,要求输出考生的编号,总排名,考场编号以及考场排名。
分析:
题意很简单嘛,一开始上来就,一组组输入,一组组排序并记录组内排名,然后再来个总排序并算总排名,结果发现最后一个测试点超时。
发现自己一开始太傻太盲目,其实只要一次性全部输进来,记录好考场编号,一次排序就可以了。既然只排了一次,怎么计算考场排名呢,这里我用了三个数组
int g_rank[];//记录各个考场当前排到的名次 (当前最后一个人的名次)
int g_score[];//记录个考场当前排到的最后一个人的分数
int g_num[];//记录个考场当前已经排好队的人数
帮助计算考场排名
//计算分组排名
int p=a[i].num;//他属于第p组
if(g_rank[p]==){//如果他是本小组第一名
a[i].rank=;
g_rank[p]=;//当前组排到了第几名
g_score[p]=a[i].score;//本小组目前排下来最后一名的分数
g_num[p]=;//当前组排到了第几个人
}else{
g_num[p]++;//更新人数
if(g_score[p]==a[i].score) {//如果此人与本组的上一人的分数相同
a[i].rank=g_rank[p];//就是本小组上一名的名次
}else{//不同的话
a[i].rank=g_num[p];//那么他的名次是本组的人数
g_rank[p]=g_num[p];//更新当前本组最后一人名次
g_score[p]=a[i].score;//更新分数
}
}
AC代码:
#include<bits/stdc++.h>
using namespace std;
struct node{
string name;
int score;
int num;
int rank;
int frank;
}a[];
bool cmp(node x,node y){
if(x.score==y.score){
return x.name<y.name;
}else{
return x.score>y.score;
}
}
int g_rank[];//记录各个考场当前排到的名次 (当前最后一个人的名次)
int g_score[];//记录个考场当前排到的最后一个人的分数
int g_num[];//记录个考场当前已经排好队的人数
int main(){
int n,k;
cin>>n;
int r=;
for(int i=;i<=n;i++){
cin>>k;
for(int j=;j<=k;j++){
cin>>a[r].name>>a[r].score;
a[r].num=i;//考场编号
r++;
}
}
sort(a+,a+r,cmp);
cout<<r-<<endl;
memset(g_rank,,sizeof(g_rank));
for(int i=;i<r;i++){
//全部排名
if(i==){
a[i].frank=;
}else{
if(a[i].score==a[i-].score){
a[i].frank=a[i-].frank;
}else{
a[i].frank=i;
}
}
//计算分组排名
int p=a[i].num;//他属于第p组
if(g_rank[p]==){//如果他是本小组第一名
a[i].rank=;
g_rank[p]=;//当前组排到了第几名
g_score[p]=a[i].score;//本小组目前排下来最后一名的分数
g_num[p]=;//当前组排到了第几个人
}else{
g_num[p]++;//更新人数
if(g_score[p]==a[i].score) {//如果此人与本组的上一人的分数相同
a[i].rank=g_rank[p];//就是本小组上一名的名次
}else{//不同的话
a[i].rank=g_num[p];//那么他的名次是本组的人数
g_rank[p]=g_num[p];//更新当前本组最后一人名次
g_score[p]=a[i].score;//更新分数
}
}
}
for(int i=;i<r;i++){
cout<<a[i].name<<" "<<a[i].frank<<" "<<a[i].num<<" "<<a[i].rank<<endl;
}
return ;
}
最新文章
- uva10635 LIS
- cordova-screenshot
- 重构Web Api程序(Api Controller和Entity)续篇
- 转——Android应用开发性能优化完全分析
- SPRING IN ACTION 第4版笔记-第七章Advanced Spring MVC-005- 异常处理@ResponseStatus、@ExceptionHandler、@ControllerAdvice
- WinForm实现简单的拖拽功能(C#)(2)
- 把nc v6的源码看懂
- 最大公约数(gcd):Euclid算法证明
- HTML&;CSS_基础04
- [物理学与PDEs]第1章习题7 载流线圈的磁场
- DNS解析中的A记录、AAAA记录、CNAME记录、MX记录、NS记录、TXT记录、SRV记录、URL转发等
- group_concat的使用
- 【AtCoder010】A - Addition(奇偶)
- Linux Performance 一文
- 切换svn登录账户
- Jenkins 集成 git .net 和nuget
- artemplate模板
- poj 1595 Prime Cuts
- php中 include 、include_once、require、require_once4个语言结构的含义和区别
- bzoj 1878