http://wikioi.com/problem/1063/
这题是贪心+堆。主要想练习一下堆的写法。算法导论里的方法名是heapify()等，但大家经常用更直观的down(), up()方法（向上，下调整），根据这两个方法，可以有build，insert，getmin方法。
向下调整的代码稍微需要判断一下左右子树是否越界，其他都很简单。
#include <iostream>
using namespace std;
#define LEN 10005
int num[LEN];
int size; void swap(int a, int b) {
int tmp = num[a];
num[a] = num[b];
num[b] = tmp;
} void down(int i) {
if (i > size) return;
int left = i * 2;
int right = i * 2 + 1;
int minIdx = left;
if (right <= size && num[left] > num[right]) {
minIdx = right;
}
if (left > size || num[i] <= num[minIdx])
return;
else {
swap(i, minIdx);
down(minIdx);
}
} void up(int i) {
if (i == 1) return;
if (num[i / 2] > num[i]) {
swap(i / 2, i);
up(i / 2);
}
} void build() {
for (int i = size / 2; i >= 1; i--) {
down(i);
}
} int getmin() {
swap(1, size);
size--;
down(1);
return num[size + 1];
} void insert(int x) {
size++;
num[size] = x;
up(size);
} int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> num[i];
}
size = n;
build();
int sum = 0;
while (size > 1) {
int a = getmin();
int b = getmin();
sum += a + b;
insert(a + b);
}
cout << sum << endl;
}