poj2166 Heapsort[构造递推]

构造一个n个点的大根堆让全部弹出时交换位置次数最多。

---

真心佩服我自己智商，这种题都做不出来

---

交换是在每次弹出堆顶，然后把堆尾元素置于堆顶，然后向下调整时产生的。玩样例可以发现似乎数字1每次都出现在堆最底层最右边（堆尾）？于是为了总交换数最多，肯定是要1号自顶向下交换到底次数最多，除此之外还希望它每次都跑到堆尾，这样是肯定最多的。观看堆的工作过程，发现构造出来的堆每弹出一个调整之后得到的$n-1$个元素的堆还是符合要求的，也就是说$n$个元素的答案堆可变为$n-1$元素的答案堆，于是可以从$n-1$个递推，具体过程是把弹出后调整的过程倒过来做，原来是沿顶向底路径都向上提一层（1与之交换所得），那递推就是路径每一点向下一层，1号点放$n$，$n$号点放$1$。画图很容易理解。

我    好    菜    啊

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 #define _dbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl

 using namespace std;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 char F[];int cnt;

 inline void Write(int x){

     cnt=;

     while(x)F[++cnt]=x%+'',x/=;

     while(cnt)putchar(F[cnt--]);

     putchar(' ');

 }

 const int N=5e4+;

 int a[N];

 int n;

 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);

     read(n);a[]=;

     for(register int i=,x;i<=n;++i){

         x=i-;

         while(x^)a[x]=a[x>>],x>>=;

         a[]=i,a[i]=;

     }

     for(register int i=;i<=n;++i)Write(a[i]);

     return printf("\n"),;

 }