专栏文章

题解：AT_joisc2007_score 得点 (Score)

LLan_yan
AT_joisc2007_score题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqb5igr
此快照首次捕获于
2025/12/04 01:55
3 个月前
此快照最后确认于
2025/12/04 01:55
3 个月前
查看原文
好水的一道题。
首先看题目给定的数值范围。
数字个数 n≤105n \le 10^5，不难看出时间复杂度不能为 n2n^2，也就是不能使用普通排序做法。
再看数字值域范围在 00 至 100100 之间，不难想到桶排序。
我们可以用一个桶存题目中的数字，在循环遍历一遍值域，将每个值的排名存下来即可。
那么输出时我们只要用数字的值查询存值的数组或者其他方式即可。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...