题解：AT_joisc2007_score 得点 (Score)

Lan_yan · 2025-02-08 12:54:07 · 题解

好水的一道题。

首先看题目给定的数值范围。

数字个数 n \le 10^5，不难看出时间复杂度不能为 n^2，也就是不能使用普通排序做法。

再看数字值域范围在 0 至 100 之间，不难想到桶排序。

我们可以用一个桶存题目中的数字，在循环遍历一遍值域，将每个值的排名存下来即可。

那么输出时我们只要用数字的值查询存值的数组或者其他方式即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,sum=0;
int a[N],op[105],lan[105];
int main()
{
    int i,j;
    memset(op,0,sizeof(op));
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        op[a[i]]++;
    }
    for(i=100;i>=0;i--)
    {
        if(op[i])
        {
            lan[i]=sum+1;
            sum+=op[i];
        }
    }
    for(i=1;i<=n;i++)
        printf("%d\n",lan[a[i]]);
    return 0;
}