[九度OJ]1431.Sort(寻找前m大数并排序)

原题链接：http://ac.jobdu.com/problem.php?pid=1431

题目描述：: 给你n个整数，请按从大到小的顺序输出其中前m大的数。

输入：: 每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。

输出：: 对每组测试数据按从大到小的顺序输出前m大的数。

样例输入：

5 3
3 -35 92 213 -644

样例输出：

213 92 3

题解：

　　寻找前m大数与寻找第m大数是同一问题，直接对n个数排序肯定是会超时的，这类问题有很多解法，本题采用小顶堆完成。小顶堆的堆顶元素就是最大m个元素中最小的一个。初始可以将每个值设得尽可能小(比n个数的任何数都小)，然后每次考虑一个数X，如果X比堆顶元素小，则不需要改变原来的堆，如果X比堆顶元素大，则需要用X替换堆顶元素，并同时调整堆结构。这个调整的过程的时间复杂度为O(log₂m)。

 1 #include <cstdio>
 2 #include <stdlib.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int n,m;
 7 int arr[1000001];
 8 int heap[1000001];
 9 
10 bool cmp(int a,int b)
11 {
12     if(a>b)
13         return true;
14     else
15         return false;
16 }
17 int main()
18 {
19     freopen("sort.in","r",stdin);
20     freopen("sort.out","w",stdout);
21     int p,q;
22     while(scanf("%d %d",&n,&m)!=EOF)
23     {
24         for(int i=0; i<m; i++)
25              heap[i] = -500001;
26 
27         for(int i=0; i<n; i++)
28         {
29               scanf("%d",&arr[i]);
30               if(arr[i]>heap[0])
31               {
32                   heap[0] = arr[i];
33                   p = 0;        
34                   while(p<m)
35                   {
36                       q = 2*p +1;
37                       if(q >= m)
38                         break;
39                       if((q<m-1) && (heap[q+1]<heap[q]))
40                           q =q+1;
41                       if(heap[q]<heap[p])
42                       {
43                           swap(heap[p],heap[q]);
44                           p = q;
45                       }
46                       else
47                           break;
48                   }
49               }
50         }
51 
52          
53 
54          sort(heap,heap+m,cmp);
55          for(int i=0; i<m; i++){
56               printf("%d",heap[i]);
57               if(i<m-1)
58                   printf(" ");
59          }                
60          printf("
");
61     }
62     return 0;    
63 }

View Code