学步园

本题实际上求的是n-1个数和的总和的

/*
 * UVA_10954.cpp
 *
 *  Created on: 2013年10月10日
 *      Author: Administrator
 */



#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 5010;
int n;
int a[maxn];
void sift(int i){
	a[0] = a[i];
	int k = i << 1;
	while(k <= n){
		if(k < n && a[k] > a[k+1]){
			k++;
		}

		if(a[0] > a[k]){
			a[i] = a[k];
			i = k;
			k = i << 1;
		}else{
			k = n + 1;
		}
	}

	a[i] = a[0];
}

void work(){
	int i;
	for(i = n >> 1 ; i ; i--){
		sift(i);
	}
	long long ans = 0;
	while(n!=1){
		swap(a[1],a[n--]);
		sift(1);
		a[1] += a[n+1];
		ans += a[1];
		sift(1);
	}

	printf("%lld\n",ans);
}
int main(){
	while(scanf("%d",&n)!=EOF,n){
		int i;
		for(i = 1 ; i <= n ; ++i){
			scanf("%d",&a[i]);
		}

		work();
	}

	return 0;
}