自动搬运

查看原文

来自洛谷，原作者为

	yydfj 不要打代码了，去玩明日方舟好不好

搬运于2025-08-24 22:33:04，当前版本为作者最后更新于2021-08-16 11:56:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是本蒟蒻第十次写的题解，如有错误点请好心指出！

问题简述

这道题我们可以换另一种思路去看待它，就容易理解了：

给你一个长度为 $N$ 的序列，求 $H$ 为前 $H$ 大的数。

解法综述

我们可以用桶的方法来做，用数组 $a$ 做桶来记录每个数，之后在序列里的数的范围内（$0≤$ 序列里的数 $≤10^6$）进行操作。

设 $n$ 为 $i$ 的第 $n$ 大的数，当发现 $a_i$ 有数时，则说明大小为 $i$ 的数有 $a_i$ 个，用 $n$ 将其减去。如果 $i$ 大于等于 $n$ ，则表明 $i$ 为前 $i$ 大的数，将 $i$ 输出即可。

代码描述

#include<cstdio>
#define max(a,b) (a>b?a:b)
int n,x,a[1000005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		a[x]++;//用数组a做桶来记录每个数
	}
	for(int i=0;i<=1000000;i++)
	{
		n-=a[i];//n为i的前n大的数，ai为大小为i的数的数量
		if(i>=n)//如果i为至少第i大的数
		{
			printf("%d",i);//输出结果，结束程序
			return 0;
		}
	}
	return 0;
}