POJ 2166 - Heapsort

http://poj.org/problem?id=2166

概要

ソートすると \(1, 2, \ldots, n\) となるような配列のうち、ヒープソートを行ったときに shifting operation における入れ替えの回数が最大となるような配列を答える。

制約

• \(1 \le n \le 5 \cdot 10 ^ 4\)

解法

各ステップで入れ替えの回数を最大にするには、shifting operation を行うときにルートに 1 があればよく、 そのためには extract-max のときに 1 が a[i] の位置にあればよい。 そのようにしながら、ヒープソートの逆を行えばよい。

なぜか G++ だと TLE したけど C++ だと通った。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   scanf("%d", &N);
 9   static int a[50001];
10   for (int n = 1; n < N; n++) {
11     a[1] = n;
12     a[n] = 1;
13     for (int i = n; i != 1; i /= 2) {
14       swap(a[i/2], a[i]);
15     }
16   }
17   a[N] = 1;
18   printf("%d", N);
19   for (int i = 2; i <= N; i++) {
20     printf(" %d", a[i]);
21   }
22   putchar('\n');
23   return 0;
24 }