HDU 1425 sort

堆排序

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1425

关于堆排序讲解详看http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html

代码跑了562MS 实在是仰慕用93MS跑出来的

这个题还必须用C交用GCC交会TLE

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define  N 1000005
 5 int a[N];
 6 void heapadjust(int *a,int i,int n)
 7 {
 8     int lchild=2*i,rchild=2*i+1;
 9     int max=i,t;
10     if(i<=n/2)
11     {
12         if(lchild<=n&&a[lchild]>a[max])
13     {
14         max=lchild;
15     }
16     if(rchild<=n&&a[rchild]>a[max])
17     {
18         max=rchild;
19     }
20     if(max!=i)
21     {
22         t=a[i];a[i]=a[max];a[max]=t;
23         heapadjust(a,max,n);
24     }
25     }
26 }
27 void heapbuild(int *a,int n)
28 {
29     int i;
30     for(i=n/2;i>=1;i--)
31     {
32         heapadjust(a,i,n);
33     }
34 }
35 void heapsort(int *a,int n)
36 {
37     int i,t;
38     heapbuild(a,n);
39     for(i=n;i>=1;i--)
40     {
41         t=a[1];a[1]=a[i];a[i]=t;
42         heapadjust(a,1,i-1);
43     }
44 }
45 int main()
46 {
47     int i,n,m;
48     while(scanf("%d %d",&n,&m)!=EOF)
49     {
50         for( i=1;i<=n;i++)
51     {
52         scanf("%d",&a[i]);
53     }
54     heapsort(a,n);
55     for(i=n;i>n-m+1;i--)
56     {
57         printf("%d ",a[i]);
58     }
59     printf("%d",a[n-m+1]);
60     puts("");
61     }
62     return 0;
63 }