学步园

每次合并最小的两堆就行了，自己觉得是用的线段树，不过yiyi说这是RMQ。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <assert.h>
#include <algorithm>
#define MAX 1234567890
#define MIN -1234567890
#define eps 1e-8

using namespace std;

const int maxn = 10010;
long long sum[maxn<<2];

void pushup(int rt)
{
        if(sum[rt<<1] == -1) sum[rt] = sum[rt<<1|1];
        else if(sum[rt<<1|1] == -1) sum[rt] = sum[rt<<1];
        else sum[rt] = min(sum[rt<<1], sum[rt<<1|1]);
}

void build(int l, int r, int rt)
{
        if(l == r)
        {
                scanf("%d", &sum[rt]);
                return ;
        }
        int m = (l + r) >> 1;
        build(l, m, rt<<1);
        build(m+1, r, rt<<1|1);
        pushup(rt);
}

void update(int p, int rep, int l, int r, int rt)
{
        if(l == r)
        {
                sum[rt] = rep;
                return ;
        }
        int m = (l + r) >> 1;
        if(p <= m) update(p, rep, l, m, rt<<1);
        else update(p, rep, m+1, r, rt<<1|1);
        pushup(rt);
}

int query(int x, int l, int r, int rt)
{
        if(l == r) return l;
        int m = (l + r) >> 1;
        if(x == sum[rt<<1]) return query(x, l, m, rt<<1);
        else return query(x, m+1, r, rt<<1|1);
}

int main()
{
        #ifdef BellWind
        freopen("10372.in", "r", stdin);
        #endif // BellWind

        int n;
        while(~scanf("%d", &n))
        {
                long long ans = 0;
                build(1, n, 1);
                int pos;
                for(int i = 1; i < n; i++)
                {
                        int h1 = sum[1];
                        ans += h1;
                        pos = query(h1, 1, n, 1);
                        update(pos, -1, 1, n, 1);
                        int h2 = sum[1];
                        ans += h2;
                        pos = query(h2, 1, n, 1);
                        update(pos, h1+h2, 1, n, 1);
                }
                printf("%lld\n", ans);
        }

        return 0;
}