关于算法-数据结构:PAT甲级1025PAT-Ranking

题目粗心

有 N 个考场, 每个考场有 K 个考生。当初给出各个考场中考生的准考证号与分数，要求将所有考生按分数从高到低排序，并按程序输入所有考生的准考证号、排名、考场号以及考场内排名。

算法思路

这是一道比拟惯例的排序题目，题目要求获取每一个考场的考生本考场的排名和最终所有考生在一起的最终排名，那么就先应用
vector<Student> students[N+1] 来保留每一个考场的考生，而后应用 vector<Student> stu 保留所有考场的考生汇合，首先对于考场 i 的学生 stuents[i] 应用 sort 函数间接进行排序获取排名，而后将获取了本地考场排名的学生增加进 stu 中，而后再对 stu 进行排序，获取每一个考生的最终排名，最初依照题目要求进行输出即可。

获取排名的办法

对于排序后第一个考生名次为 1，而后对于其余考生若与前一个考生的分数雷同取得雷同排名，否则等于排在后面的人数加 1。

留神点

1. 考生编号为 13 位须要应用字符数组或者字符串进行存储。
2. 这里应用了 string 类型进行存储，输出的时候先应用字符数组进行输出，而后间接赋值给 string 类型变量，这样在数据量较高的应用比 cin 输出要快, 输出的时候得应用 c_str()函数转化为字符数组进行输入.

提交后果

实现代码

#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int N;// 考场数目
int K;// 每一个考场的人数

struct Student{
    string registration_number;// 考生编号,13 位
    int total_score; // 总分
    int location_number; // 考场编号, 从 1 开始
    int local_rank; // 本考场排名
    int final_rank; // 最终排名
};

bool cmp(Student a,Student b){if (a.total_score!=b.total_score){return a.total_score>b.total_score;} else{return a.registration_number<b.registration_number;}
}

int main(){scanf("%d",&N);
    vector<Student> students[N+1]; // 所有考生的汇合,studnets[i]就是考场编号为 i 的考生汇合
    vector<Student> stu; // 所有考生汇合
    int index = 0;
    char registration_number[15];
    for (int i = 1; i <=N; ++i) {scanf("%d",&K);
        for (int j = 0; j < K; ++j) {
            Student student;
            scanf("%s %d",registration_number,&student.total_score);
            student.registration_number = registration_number;
            student.location_number = i;
            students[i].push_back(student);
        }
    }
    // 首先对本考场的学生进行排序获取排名
    for (int i = 1; i <= N; ++i) {sort(students[i].begin(),students[i].end(),cmp);
        // 计算排名
        for (int j = 0; j < students[i].size(); ++j) {if (j==0){students[i][j].local_rank = 1;// 第一个排名为 1
            } else if (students[i][j].total_score==students[i][j-1].total_score){
                // 总分一样排名一样
                students[i][j].local_rank = students[i][j-1].local_rank;
            } else{
                // 总分不一样，排名为后面的人数加一
                students[i][j].local_rank = j+1;
            }
            // 计算完本考场排名后退出 stu 中，获取最终排名
            stu.push_back(students[i][j]);
        }
    }
    // 对所有考生进行排序
    sort(stu.begin(),stu.end(),cmp);
    // 获取考生的总排名
    for (int k = 0; k < stu.size(); ++k) {if (k==0){stu[k].final_rank = 1;
        } else if (stu[k].total_score==stu[k-1].total_score){stu[k].final_rank = stu[k-1].final_rank;
        } else{stu[k].final_rank = k+1;
        }
    }
    // 输入所有考生的信息
    printf("%d\n",stu.size());
    for (int l = 0; l < stu.size(); ++l) {printf("%s %d %d %d\n",stu[l].registration_number.c_str(),stu[l].final_rank,stu[l].location_number,stu[l].local_rank);
    }
    return 0;
}