2010年03月29日星期一.pku2166 構(gòu)造
題意:要求一個(gè)序列，使這個(gè)序列進(jìn)行heapsort 進(jìn)行交換的次數(shù)最大。
我看到題目中有兩個(gè)樣例輸出
n = 5: 5 4 3 2 1
n = 6: 6 5 3 2 4 1
我發(fā)現(xiàn)如果把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?