1235：輸出前k大的數(shù)

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 12715 ??? 通過數(shù): 4043

【題目描述】

給定一個數(shù)組，統(tǒng)計前k大的數(shù)并且把這k個數(shù)從大到小輸出。

【輸入】

第一行包含一個整數(shù)n，表示數(shù)組的大小。n < 100000。

第二行包含n個整數(shù)，表示數(shù)組的元素，整數(shù)之間以一個空格分開。每個整數(shù)的絕對值不超過100000000。

第三行包含一個整數(shù)k，k < n。

【輸出】

從大到小輸出前k大的數(shù)，每個數(shù)一行。

【輸入樣例】

10 4 5 6 9 8 7 1 2 3 0 5

【輸出樣例】

9 8 7 6 5

【分析】

? ? ? ? 這道題很好求解，實際上就是將給定的數(shù)進行排序，然后將前k大的數(shù)輸出即可。排序算法有很多種，最簡單的方法是C++用sort函數(shù)，C語言用qsort函數(shù)即可。

? ? ? ? 這道題被放到分治法專題，即將大問題轉(zhuǎn)化為小問題，分治法排序一般就是快速排序、歸并算法和堆算法。其中歸并算法可以參見1182：合影效果，這里我們就用堆算法實現(xiàn)。堆算法的原理請見文章：圖解排序算法（三）之堆排序。

【參考代碼】

#include<stdio.h> #define N 100010 int a[N];void swap(int arr[],int i,int j) //交換樹中兩個結(jié)點值 {int tmp;tmp=arr[i];arr[i]=arr[j];arr[j]=tmp; } void heapify(int tree[],int n,int i) //調(diào)整小根數(shù) {int c1,c2,min;if(i>=n)return;c1=2*i+1;c2=2*i+2;min=i;if(c1<n && tree[c1] < tree[min])min=c1;if(c2<n && tree[c2] < tree[min])min=c2;if(min!=i){swap(tree,min,i);heapify(tree,n,min);} } void build_heap(int tree[],int n) //建小根數(shù) {int last_node = n-1;int parent = (last_node-1)/2;int i;for(i=parent;i>=0;i--)heapify(tree,n,i); } void heap_sort(int tree[],int n) //堆排序 {int i;build_heap(tree,n);for(i=n-1;i>=0;i--){swap(tree,i,0);heapify(tree,i,0);} } int main() {int i;int n,k;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d\n",&a[i]);heap_sort(a,n);scanf("%d",&k);for(i=0;i<k;i++)printf("%d\n",a[i]);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1235

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1235：输出前k大的数）——堆排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。