ソートダウン----------------------

ここをクリックして杭電の上のテスト問題に入りますここをクリックして厦大のテスト問題に入ります
杭電の問題はヒルソート+Hibbard増分シーケンスでは通れない.コードは以下の通りです(テストなので少し乱れています)

 1 #include<stdio.h>                  //     /    
 2 #include<algorithm>
 3 using namespace std;
 4 int a[1000011],i,j,m,n,t,d,p,q,tmp;
 5 int main()
 6 {
 7     while(scanf("%d%d",&t,&q)!=EOF)
 8     {
 9         for(i=0;i<t;i++)
10             scanf("%d",&a[i]);
11         for(d=(t/2)-1;d>0;d=d/2)  //   n/2    d d=1
12         {
13             for(p=d;p<t;p++)   //         .
14             {
15                 tmp=a[p];
16                 for(i=p;i>=d&&a[i-d]<tmp;i=i-d)
17                 {
18                     a[i]=a[i-d];
19                 }
20                 a[i]=tmp;
21             }
22         }
23         for(i=0;i<t-1;i++)
24             printf("%d ",a[i]);
25         printf("%d
",a[t-1]);
26     }
27 }

しかし、急速に水を並べ替えた.

 1 // ,  904   .           
 2 #include<stdio.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int a[1000011],i,j,m,n,t,d,p,q,tmp;
 6 int main()
 7 {
 8     while(scanf("%d%d",&t,&q)!=EOF)
 9     {
10         for(i=0;i<t;i++)
11             scanf("%d",&a[i]);
12         sort(a,a+t);
13         for(i=t-1;i>t-q;i--)
14             printf("%d ",a[i]);
15         printf("%d
",a[t-q]);
16     }
17 }

これはstlの速いソートの他の人のコード//私はまだ見ていないで後で再び書きます.

 1 #include <stdio.h>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 static int a[1000000];
 7 
 8 int main()
 9 {
10     int i,n,m;
11     while(EOF != scanf("%d %d",&n,&m))
12     {
13         for(i=0;i<n;i++)
14             scanf("%d",&a[i]);
15         make_heap(a,a+n);
16         printf("%d",a[0]);
17         for(i=1;i<m;i++)
18         {
19             pop_heap(a,a+n-i+1);
20             printf(" %d",a[0]);
21         }
22         printf("
");
23     }
24     return 0;
25 }

 
ビルの大きいヒルと速い列については

 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[1000011],i,j,m,n,t,d,p,tmp;
 5 int main()
 6 {
 7     while(scanf("%d",&t)!=EOF)
 8     {
 9         for(i=0;i<t;i++)
10             scanf("%d",&a[i]);
11         for(d=(t/2)-1;d>0;d=d/2)  //   n/2    d d=1
12    {
13        for(p=d;p<t;p++)   //         .
14        {
15            tmp=a[p];
16            for(i=p;i>=d&&a[i-d]>tmp;i=i-d)
17            {
18                 a[i]=a[i-d];
19            }
20            a[i]=tmp;
21        }
22    }
23         for(i=0;i<t-1;i++)
24             printf("%d ",a[i]);
25         printf("%d
",a[t-1]);
26     }
27 }
28 /**************************************************************
29     Problem: 1004
30     User: xpower
31     Language: C++
32     Result: Accepted
33     Time:700 ms
34     Memory:4940 kb
35 ****************************************************************/

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1000011],i,j,m,n,t;
int main()
{
    while(scanf("%d",&t)!=EOF)
    {
        for(i=0;i<t;i++)
            scanf("%d",&a[i]);
        sort(a,a+t);
        for(i=0;i<t-1;i++)
            printf("%d ",a[i]);
        printf("%d
",a[t-1]);
    }
}
/**************************************************************
    Problem: 1004
    User: xpower
    Language: C++
    Result: Accepted
    Time:508 ms
    Memory:4944 kb
****************************************************************/