题解：AT_joisc2007_score 得点 (Score)

· · 题解

题目传送门。

题目涉及算法

计数思想。

大致题意

输入 n 个 0 ～ 100 之间的整数，将它们从大到小排序，输出它们的排名（输入顺序输出）。

注意事项：

相同的整数名次相同，因此可能存在中间某个名次没有对应的整数。

思路解析

使用计数思想，将 to[i] 作为 i 在数列中存在的次数。

再次让 i 遍历 1 \sim n 每次从 a[i]+1 找到 100 （最大值），将它们的 to 数组累加，最后加上 1 （最大的数是第 1 名而不是第 0 名）。输出它们的加和。

详见以下代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010],to[110];//只有100个数，to数组开100。
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        to[a[i]]++;//计数
    }
    for(int i=1;i<=n;i++)
    {
        int cnt=1;//从第一名开始
        for(int j=a[i]+1;j<=100;j++) cnt+=to[j];
        cout<<cnt<<endl;
    }
    return 0;
}

时间复杂度： O(100n) 。