7.4 排序的实际应用

“在现实生活中，排序有很多用途，”我继续解释，”比如学校排名次、公司招聘划分数线等。”

7.4.1 学员的名次

题目描述： 期末考试语文成绩出来了，老师在课堂上公布了每位同学的语文成绩，小明想查一下自己的成绩在班级能排到第几名。请你编写一个程序，根据给定的所有同学的语文成绩以及小明的语文成绩，计算出小明的排名。

输入格式： 第一行一个整数 n 代表学生总人数（ n≤100 ）；第二行，有 n 个整数，代表 n 个语文成绩（这些成绩都是 0∼100之间的分数）；第三行一个整数 x 代表小明同学的语文成绩。

输出格式： 一个整数，代表小明同学的名次。

样例输入：

5
98 100 99 80 87
98

样例输出：

3

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[110], n;
    cin >> n;
    
    for(int i = 1; i <= n; i++) 
        cin >> a[i];  // 输入所有成绩
    
    int x;
    cin >> x;  // 输入小明的成绩
    
    // 冒泡排序，按降序排列
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n-i; j++){
            if(a[j] < a[j+1])
                swap(a[j], a[j+1]);
        }
    }
    
    // 查找小明成绩的排名
    for(int i = 1; i <= n; i++){
        if(a[i] == x){
            cout << i;  // 输出排名（位置）
            break;
        }
    }
    return 0;
}

算法解析：

1. 将所有成绩按降序排列
2. 在排序后的数组中查找小明的成绩
3. 找到的位置就是小明的排名

7.4.2 分数线的划定

题目描述： 宇航局准备招收一批科研人员从事月球探索的航空科研工作。这个职位来了很多应聘者，宇航局对众多应聘者进行综合素质考试，最终会选出 x 名综合得分排名靠前应聘者。目前考试已经结束了，宇航局需要根据目前考试的成绩计算出，如果要选出 x 个分数靠前的人，分数线应该划到多少分？

输入格式： 第一行是一个整数 n ，代表参加考试的人数。（n≤1000）第二行有 n 个整数，用空格隔开，代表 n 个人的考试分数。（注意：不存在成绩一样的分数）第三行有一个整数 x （x<n），代表宇航局要选出的人数。

输出格式： 一个整数，代表如果要选出 x 个人，宇航局应当划出的分数线。

样例输入：

8
100 90 98 92 85 70 88 96
2

样例输出：

98

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[1010], n;
    cin >> n;
    
    for(int i = 1; i <= n; i++) 
        cin >> a[i];  // 输入所有考试分数
    
    int x;
    cin >> x;  // 输入要选出的人数
    
    // 冒泡排序，按降序排列
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n-i; j++){
            if(a[j] < a[j+1])
                swap(a[j], a[j+1]);
        }
    }
    
    cout << a[x];  // 第x名的分数就是分数线
    return 0;
}

算法解析：

1. 将所有分数按降序排列
2. 第x个位置的分数就是分数线
3. 这个分数线保证前x名都能被录取