【OJ】贪心法 Fence Repair POJ 3253 霍夫曼（Huffman）编码原理 acmclub 12326

题目链接：点击打开链接

/*
	贪心法 Fence Repair POJ 3253
	霍夫曼（Huffman）编码原理
*/
#include<iostream>
#include<algorithm>
typedef long long LL;
using namespace std;
int l[50010];
int main(){
    int j,m=0,n;cin>>n;
    LL s=0,ans=0;
    for(int i=0;i<n;i++)cin>>l[i];
    l[n]=2100000000;/*哨兵*/
    sort(l,l+n);ans=s=l[0]+l[1];
    while(n-m>2){
//    	l[++m]=s;
//    	sort(l+m,l+n);        // O(n*lg(n))
	m++;
	for( j=m;l[j]<s;j++){ // O(n)
        	l[j]=l[j+1];}
	l[--j]=s; 

    	s=l[m]+l[m+1];
    	ans+=s;
//      for( j=0;j<6;j++)cout<<l[j]<<" ：";cout<<s<<" "<<ans<<endl;
    }
 // for( j=0;j<6;j++)cout<<l[j]<<" :";cout<<s<<" "<<ans<<endl;
    cout<<ans<<endl;
    return 0;
}