题目

话说3008年的Orz教主节，全民狂欢，传递教主圣火，以致万人空巷，股票飞涨。真乃锣鼓喧天，鞭炮齐鸣，红旗招展，人山人海呐。可是小X为了准备NOIP3008，不得不待在家里好好Coding。小X希望早点结束当天的任务，加入圣火传递队伍中去。
在这个不亚于狂欢节的日子里，小X的老师却“公然违抗”休假法令，布置小X写一个小根堆，但是小X不会堆的操作，所以想了一个偷懒的办法：
　　堆是一棵完全二叉树，每个结点有一个权。小根堆的根的权最小，且根的两个子树也是一个堆。可以用一个数组a来记录一棵完全二叉树，a[1]为根结点，若结点a[j]不是根结点，那么它的父亲为a[j/2]（取下整）；若结点a[k]不是叶子结点，那么它的左儿子为a[2k]，它的右儿子为a[2k+1]。
　　他希望一组数据按一定顺序依次插入数组中（即第i个数为a[i]），最后得出来就已经是一个堆，即不需要任何交换操作，若有多种方法，输出字典序最大的一组，显得这个数据更乱。

---

解题思路

对于当前序列，我们肯定是选最小的放在堆顶。
然后分左右子树（大的分左边，小的分右边），显然可以重复现在的选择。

---

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[70000],m,b[70000];
void fz(int l,int r,int k){b[k]=a[l]; if (l==r) return; int mid=(l+r)>>1; fz(mid+1,r,2*k); fz(l+1,mid,2*k+1); 
}
int main(){scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); fz(1,n,1); for(int i=1;i<n;i++) printf("%d ",b[i]); printf("%d\n",b[n]); 
}