数学家伯利亚在《怎样解题》里说过的解题步骤第二步就是迅速想到与该题有关的原型题。（积累的重要性！）
对于这道题，可以发现其实和huffman算法的思想很相似（可能出题人就是照着改编的）。当然最后只是输出cost，就没必要建树什么的了。只要理解了huffman算法构造最优二叉树的思路，就按那么想就知道每个a[i]要加多少次了。
当然这道题没想到这些也可以找出规律的，就是一种贪心思想。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<map> #include<set> #include<vector> #include<algorithm> #include<stack> #include<queue> using namespace std; #define INF 1000000000 #define eps 1e-8 #define pii pair<int,int> #define LL long long int const int maxn=310009; int n; LL ans=0,a[maxn]; int main() { //freopen("in6.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%I64d",&a[i]); } sort(a+1,a+n+1); for(int i=1;i<=n-1;i++) ans+=(i+1)*a[i]; ans+=n*a[n]; cout<<ans<<endl; }
Codeforces Round #263 (Div. 2)C(贪心，联想到huffman算法)
原文：http://www.cnblogs.com/zywscq/p/3940424.html