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\n",heap[i]);    }    return 0;}