P7785 [COCI2016-2017#6] Hindeks 题解

yydfj · 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;
}