(贪心5.2.2)UVA 10954 Add All(利用数据的有序化来进行贪心选择)

本题实际上求的是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;}