首页 > 代码库 > Vijos1788 第K大

Vijos1788 第K大

2024-10-20 03:52:39   212人阅读

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)的复杂度得到结果，代码如下（题设数据貌似用排序也能过）

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int MAXN=4e4;
 6 int num[MAXN];
 7 int n,k;
 8 void Init()
 9 {
10     for(int i=0;i<MAXN;i++)
11         num[i]=-1;
12     for(int i=0;i<n;i++)
13     {
14         int temp;
15         scanf("%d",&temp);
16         if(num[temp]>=1)
17             num[temp]++;
18         else num[temp]=1;
19     }
20 }
21 void Solve()
22 {
23     int temp=0;
24     for(int i=MAXN-1;i>=0;i--)
25     {
26         if(num[i]>=1) 
27         {
28             //printf("%d\n",i);
29             temp+=num[i];
30         }
31         if(temp>=k)
32         {
33             printf("%d\n",i);
34             break;
35         }
36     }
37 }
38 int main()
39 {
40     while(scanf("%d%d",&n,&k)!=EOF)
41     {
42         Init();
43         Solve();
44     }
45     return 0;
46 }

 

Vijos1788 第K大


联系
我们