Vijos1788 第K大 [模拟]

1.题意：给定N个数字，和一个值K，要求输出一组数据中第K大的数字，其中30%的测试点满足：n <= 100;60%的测试点满足：n <= 1000;100%的测试点满足：n <= 100000;1 <= k <= n, 每个同学的分数在[0,32767]之间;

2.分析：最朴素的想法是对数据排序，然后直接得出结果，不过一般的sort()函数复杂度为O(nlogn),不是很快。这里可以注意到，输入数据的范围并不大，在1e4这个数量级，这样我们开一个4e4的数组，读入数据时，用数组[i]表示i这个数是否在数据中以及出现了几次，这样能以O(n)的复杂度得到结果，代码如下（题设数据貌似用排序也能过）

# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int MAXN=4e4;
int num[MAXN];
int n,k;
void Init()
{
    for(int i=0;i<MAXN;i++)
        num[i]=-1;
    for(int i=0;i<n;i++)
    {
        int temp;
        scanf("%d",&temp);
        if(num[temp]>=1)
            num[temp]++;
        else num[temp]=1;
    }
}
void Solve()
{
    int temp=0;
    for(int i=MAXN-1;i>=0;i--)
    {
        if(num[i]>=1) 
        {
            //printf("%d
",i);
            temp+=num[i];
        }
        if(temp>=k)
        {
            printf("%d
",i);
            break;
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        Init();
        Solve();
    }
    return 0;
}