2010年03月29日星期一.pku2166 构造
题意:要求一个序列，使这个序列进行heapsort 进行交换的次数最大。
我看到题目中有两个样例输出
n = 5: 5 4 3 2 1
n = 6: 6 5 3 2 4 1
我发现如果把6去掉，换上1，再翻下去就是5。
于是我想好像可以递推，然后就过了。。
POJ bug真多，下面的代码第一次交TLE，第二次375MS
1
2 const int N = 50100;
3 int a[N],n,len;
4 int main()
5 {
6 int i,j,k;
7 scanf("%d",&n);
8 a[1] = 1,len = 1;
9 for (k = 2;k <= n;k++) {
10 i = len;
11 while (i > 1) {
12 a[i] = a[i/2];
13 i /= 2;
14 }
15 a[1] = k;
16 a[++len] = 1;
17 }
18 for (i = 1;i <= len;i++) {
19 printf("%d ",a[i]);
20 }
21 putchar(10);
22 return 0;
23 }
24