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=;i<MAXN;i++)

         num[i]=-;

     for(int i=;i<n;i++)

     {

         int temp;

         scanf("%d",&temp);

         if(num[temp]>=)

             num[temp]++;

         else num[temp]=;

     }

 }

 void Solve()

 {

     int temp=;

     for(int i=MAXN-;i>=;i--)

     {

         if(num[i]>=)

         {

             //printf("%d\n",i);

             temp+=num[i];

         }

         if(temp>=k)

         {

             printf("%d\n",i);

             break;

         }

     }

 }

 int main()

 {

     while(scanf("%d%d",&n,&k)!=EOF)

     {

         Init();

         Solve();

     }

     return ;

 }

巴特西

Vijos1788 第K大 [模拟]

最新文章

热门文章