poj 2166 构造

一个看了解题报告才能想明白的题目，第一点比较容易想明白，就是每次把1交换到堆顶之后如果能够换到最后面的位置那么一定是最优的，但是怎么实现这个没有想明白。

题解的那种构建方法，及从2开始插入，是可以保证达到上述效果的，这个自己想想就能明白。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=5e4+9;
int heap[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int t=i;
        while(t>1)
        {
            heap[t]=heap[t>>1];
            t>>=1;
        }
        heap[t]=i+1;
    }
    heap[n]=1;
    for(int i=1;i<=n;i++)
    {
        if(i!=n)
        printf("%d ",heap[i]);
        else
        printf("%d
",heap[i]);
    }

    return 0;
}