首页 > 学院 > 开发设计 > 正文

PAT-A 1025. PAT Ranking (25)

2019-11-06 09:17:35
字体:
来源:转载
供稿:网友

题目链接在此。

题意理解

有N个考场,每个考场有若干个学生。现给出各个考场中考生的准考证号与分数,要求所有考生按分数从高到低排序,并按顺序输出所有考生的准考证号、最终排名、考场(组)号、考场内排名。

思路

首先说明一下自己的思路

定义一个结构体数组(二维,第一维表示考场号-1),结构体成员见代码; 读取并保存输入; 对同一个考场内的考生成绩进行排序,将数组中每个成员的考场排名写入自己的结构体成员; 将二维数组转换成一维数组(方便使用sort函数),对所有考生进行排序,并将排名写入自己的结构体成员; 按照题目要求输出信息

注意:当分数相同时,按照准考证号从小到大排序。

《算法笔记》思路:

《算法笔记》的大致思路和以上出不多,由于为了使用sort函数,多了一步数组降维的操作,所以干脆将数组直接定义为一维数组,这时需要在进行组内排序的时候需要注意该组的起始点。

由于在进行全部考生排序之前,所有解题需要的信息已经拿到,为了简化代码,可以直接一遍给所有考生排序,一遍输出相应的信息。

AC代码

#include<cstdio> #include<iostream>#include<algorithm>#include<cstring>using namespace std;struct INFO{ char id[14]; //id registration numbers int grade; //分数 int rank_final; //最终排名 fianl_rank int rank_local; //区间内的排名 local_rank int lnum; //输出区间 location_number}stu[101][305];//排名函数bool cmp(INFO a, INFO b){ if(a.grade!=b.grade) return a.grade > b.grade; else return (strcmp(a.id, b.id) < 0);}int main(){ int N,K; scanf("%d",&N); int sum = 0; //记录总的参赛队员数 int num = 0; //记录是第几组 int pnum[N]; //记录每一组的人数 for(int time = 0 ; time < N; time++){ scanf("%d",&K); pnum[num] = K; sum += K; getchar(); //吸收换行符 for(int i = 0 ;i < K; i++){ scanf("%s %d", &stu[num][i].id, &stu[num][i].grade); stu[num][i].lnum = time+1; } //计算组内排名 //需要:1.先排序,2.然后才能确定排名 //1.排序 sort(stu[num],stu[num]+K,cmp); //2.确定组内排名 stu[num][0].rank_local = 1; for(int i = 1; i < K; i++){ if(stu[num][i].grade == stu[num][i-1].grade){ stu[num][i].rank_local = stu[num][i-1].rank_local; }else{ stu[num][i].rank_local = i+1; } } num++; } //最终排名 //1.需要先将二维数组变成一维数组才能用sort函数 //2.之后同组内排名方法 //1. INFO fstu[N*301]; int index = 0; for(int i = 0 ; i < N; i++){ for( int j = 0 ; j < pnum[i]; j++){ fstu[index++] = stu[i][j]; } } //2.sort for all & confirm final rank sort(fstu,fstu+index,cmp); fstu[0].rank_final = 1; for(int i = 1; i < index; i++){ if(fstu[i].grade == fstu[i-1].grade){ fstu[i].rank_final = fstu[i-1].rank_final; } else{ fstu[i].rank_final = i+1; } } //PRint result printf("%d/n",sum); for(int i = 0; i < index; i++){ printf("%s %d %d %d/n",fstu[i].id, fstu[i].rank_final, fstu[i].lnum, fstu[i].rank_local); } return 0;}

排序题一般解题思路看这里。


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表