9度OJ 题目1371：最小的K个数

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

题目描述：

输入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 44 5 1 6 2 7 3 8

样例输出：

1 2 3 4                                                                                                                                               

思路：

面对如此规模的n，k采用一般方法肯定会超时的，我们维护一个K个元素的最大堆，（前K个元素初始化建堆），然后每次读入一个元素，就和堆顶元素相比较

如果该元素比堆顶元素大，那么跳过，否则更新堆顶元素，并调整堆，这样一遍之后，我们得到了最小的K个元素构成的最大堆，再排序即可。

代码：

#include<iostream>#include<algorithm>#include<cstdlib>#include<cstdio>using namespace std;const int MAX=200001;int min_k[MAX];void heap_adj(int *a,int i,int len){int index=i*2;int p=2*i,q=p+1;if(q<=len && a[p]<a[q]) index=q;if(index<=len && a[i]<a[index]){swap(a[i],a[index]);heap_adj(a,index,len);}}void makeheap(int *a,int len){for(int i=len/2;i>=1;i--)heap_adj(a,i,len);}int main(){int n,k;while(cin>>n>>k){for(int i=1;i<=k;i++)scanf("%d",&min_k[i]);makeheap(min_k,k);for(int i=k+1;i<=n;i++){int tmp;scanf("%d",&tmp);if(tmp<min_k[1]){min_k[1]=tmp;heap_adj(min_k,1,k);}}sort(min_k+1,min_k+1+k);for(int i=1;i<k;i++) cout<<min_k[i]<<" ";cout<<min_k[k]<<endl;}return 0;}