NOIp中很少見的數(shù)據(jù)結(jié)構(gòu)的題目，可以用堆實(shí)現(xiàn)，也可以用兩條隊(duì)列. 用堆實(shí)現(xiàn)，調(diào)了很久 = =
需要注意down函數(shù)的邊界問題.
1
#include<stdio.h>
2#include<string.h>
3#include<iostream>
4using namespace std;
5int n, h[10010];
6
struct heap
{
7
void swap(int*i, int*j){
8
int k = *i; *i = *j; *j = k;
9
}
10 void up(int k){
11 while (k > 1)
12 if (h[k/2] > h[k]) {
13 swap(&h[k/2], &h[k]);
14 k /= 2;
15 }else break;
16 }
17 void down(int k){
18 while (2*k <= n){
19 int l = 2*k, r = l<n ? l+1 : l;
20 if (h[r] < h[l]) l++;
21 if (h[k] > h[l]){
22 swap(&h[k], &h[l]);
23 k = l;
24 }else break;
25 }
26 }
27 void insert(int x){
28 h[++n] = x;
29 up(n);
30 }
31 void del(int k){
32 swap(&h[k], &h[n--]);
33
34 down(k);
35 }
36 int pop(){
37 del(1);
38 return h[n+1];
39 }
40
};
41heap hp;
42int main(){
43 int i, sum = 0;
44 scanf("%d", &n);
45 for (i = 1; i <= n; i++)
46 scanf("%d", &h[i]);
47 for (i = n/2; i > 0; i--) hp.down(i);
48 while (n > 1){
49 int x = hp.pop(), y = hp.pop();
50 sum += x+y;
51 hp.insert(x+y);
52 }
53 printf("%d\n", sum);
54}
55