学步园

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 3↵ 1 2 9↵	以文本方式显示 15↵	1秒	64M	0

     据说这道题是以前的一个noip题，这道题用调用stl里面的优先队列可以直接秒杀掉的，看到大家的代码平均行数是37行，大概用的库吧。本着学习的目的查了一些资料，我自己手写了一个最小【堆（优先队列）】，

 首先说一下这道题用到的基本的操作：就是插入和删除，这道题的本质就是插入和删除一个节点后维护这个完全二叉树的问题。和大家的思路一样插入的时候是把节点插入到最后一个位置然后和父亲节点比较，如果比

父亲节点小，则和父亲节点交换，变成当前节点，然后进行递归操作，直到没有交换。这样插入节点后，就维护了这颗二叉树，时间复杂度为lgn。删除操作就是把堆顶点删除后，把最后一个节点移到堆顶点，然后进行

晒落操作，然后这样就可以完成了删除一个堆顶点后的维护操作。

        当最大堆的时候只不过是判断条件换了一下，其他的操作一样。最大堆是父节点的元素小于子节点的。

       当利用上面的删除和维护操作的时候就可以实现一个堆排序。复杂度为nlgn。还是比较理想的。

       其他的一些小细节是，因为用数组操作的从1开始，所以，每个节点编号x的父亲节点编号是floor(x)，其左孩子和右孩子的节点编号为2*x 和 2 * x + 1。还有些注意的是在编代码的时候边界的问题，我就在边界

条件上漏判了结果wa了。

       再说一点其他的吧，我原先使用的一个数组进行降序快排然后进行插入删除，操作来模拟的一个看似像是优先队列的操作，因为以前用这种方法做过去过一道哈夫曼树的问题，结果再用到此题中来，结果直接tle了

因为那样做的时间复杂度为N^2lgn。也算成长中的一个小收获吧。呵呵。。那样做也能实现优先队列的操作，但是时间复杂度高了点。没有用二叉树的效率高。要是数据量不是太大的话，还是能过去的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define Swap(a,b) a+=b; b = a-b;a -= b
#define Min(a,b) a<b?1:0
using namespace std;


//加入一个节点后维护一棵树；
void insert_node(int *input,int loc)
{

    int parent = loc/2;
    while(parent != 0)
    {
        if(input[parent] <= input[loc])
        {
            break;
        }else{
            Swap(input[parent],input[loc]);
            loc = parent;
            parent /= 2;
        }
    }
    return ;
}


//删除一个节点后,维护一棵树
void del_node(int *input,int n)
{
    int loc = 1,left = 2*loc,right = 2*loc + 1;
    input[loc] = input[n--];
    int t;
    //while(loc < n && left <=n)
    while(left <= n)
    {
        if(right <=n){
            t = Min(input[left],input[right]);
            t = (t== 1)?left:right;
        }else{
            t = left;
        }
        if(input[loc] > input[t])
        {
            Swap(input[loc],input[t]);
            loc = t;
        }else{
            break;
        }
        left = 2 * loc;
        right = 2 * loc + 1;
    }
    return ;
}


int main()
{
    int N;
    int input[10010];
    scanf("%d",&N);

    memset(input,0,sizeof(input));
    for(int i = 1;i < N+1;++i)
    {
        scanf("%d",&input[i]);

        insert_node(input,i);
    }
    long long tmp = 0,s = 0;
    while(N>1)
    {
        tmp = input[1];
        del_node(input,N);
        --N;
        tmp += input[1];
        del_node(input,N);
        input[N] = tmp;
        insert_node(input,N);
        s += tmp;
    }
    printf("%lld\n",s);
    return 0;
}