9.1 并列排名问题

“小朋友们，”我微笑着说，”在各种比赛中，经常会出现选手得分相同的情况。这时候我们需要特殊的排名方法，让我们来学习如何处理并列排名吧！”

9.1.1 允许并列的排名

题目描述： 在我们参加的各种竞赛中，允许并列的排名方式是经常遇到的。例如有四名选手的成绩分别为 50、80、50、30 分，则 80分的选手为第一名， 50 分的两名选手均为第二名，30 分的选手为第四名。 请编写一个程序，计算每个选手在这种排名方式之下的名次（分数高的选手排前面）。

输入格式： 第一行为一个整数 n ，表示参赛的选手数， 1≤n≤1000 。 第二行为 n 个整数，表示每位选手的成绩，0<=成绩<=100。

输出格式： 一行，表示每位选手的名次。

样例输入：

4 
50 80 50 30

样例输出：

2 1 2 4

代码实现：

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

int main(){
    int a[1010], n, cnt[110] = {0};  // a存储成绩，cnt统计每个分数的人数
    cin >> n;
    
    // 输入成绩并统计每个分数的人数
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[a[i]]++;  // 统计分数a[i]出现的次数
    }
    
    // 计算每个分数对应的排名
    int q = 0;  // 当前已经排过名的人数
    for(int i = 100; i >= 0; i--){  // 从高分到低分遍历
        if(cnt[i]){  // 如果这个分数有人获得
            int t = cnt[i];      // 获得这个分数的人数
            cnt[i] = q + 1;      // 这个分数的排名
            q = q + t;           // 更新已排名人数
        }
    }
    
    // 输出每个选手的排名
    for(int i = 1; i <= n; i++){
        cout << cnt[a[i]] << " ";  // 根据成绩查找对应排名
    }
    return 0;
}

算法解析：

1. 使用cnt数组统计每个分数的出现次数
2. 从高分到低分遍历，计算每个分数对应的排名
3. 排名等于前面所有人数+1，跳过的名次等于获得该分数的人数
4. 最后根据每个选手的成绩输出对应排名