九度oj 题目1371：最小的K个数

题目1371：最小的K个数

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：6646

解决：1417

题目描述：

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

输入：

每个测试案例包括2行：

第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。

第二行包含n个整数，表示这n个数，数组中的数的范围是[0,1000 000 000]。

输出：

对应每个测试案例，输出最小的k个数，并按从小到大顺序打印。

样例输入：

8 4
4 5 1 6 2 7 3 8

样例输出：

1 2 3 4
分析：为了熟练优先队列，这里直接用的优先队列，还有也可以用sort（）。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int main(){
 5     int n, k;
 6     while(scanf("%d %d", &n, &k) != EOF){
 7         int *a = new int [n];
 8         for(int i = 0; i < n; i++){
 9             scanf("%d", &a[i]);
10         }
11         sort(a, a + n);
12         printf("%d", a[0]);
13         for(int i = 1; i < k; i++)
14             printf(" %d", a[i]);
15         printf("
");
16         delete [] a;
17     }
18     return 0;
19 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct cmp{
 7     bool operator()(const long long &a, const long long &b){
 8         return a > b;
 9     }
10 };
11 
12 int main(){
13     
14     int n, k;
15     long long t;
16     while(scanf("%d %d", &n, &k) != EOF){
17         priority_queue<long long, vector<long long>, cmp> pq;
18         for(int i = 0; i < n; i++){
19             scanf("%lld", &t);
20             pq.push(t);
21         }
22         printf("%lld", pq.top());
23         pq.pop();
24         for(int i = 1; i < k; i++){
25             printf(" %lld", pq.top());
26             pq.pop();
27         }
28         printf("
");
29     }
30     return 0;
31 }

总结：有多组数据要处理，一定要把需要存放数据的容器清空！！！

这题要提升速度的话，我觉得只要搞一个大小为k的堆，每放一个数，插进去，把k+1小的数弹出，不需要将无须弹出的数建堆。