題目描述
瑞瑞想要親自修復在他的一個小牧場周圍的圍欄。他測量柵欄并發現他需要N（1≤N≤20,000）根木板，每根的長度為整數Li（1≤Li≤50,000）。于是，他神奇地買了一根足夠長的木板，長度為所需的N根木板的長度的總和，他決定將這根木板切成所需的N根木板。（瑞瑞在切割木板時不會產生木屑，不需考慮切割時損耗的長度)瑞瑞切割木板時使用的是一種特殊的方式，這種方式在將一根長度為x的模板切為兩根時，需要消耗x個單位的能量。瑞瑞擁有無盡的能量，但現在提倡節約能量，所以作為榜樣，他決定盡可能節約能量。顯然，總共需要切割N-1次，問題是，每次應該怎么切呢？請編程計算最少需要消耗的能量總和。
輸入輸出格式
輸入格式：第一行: 整數N，表示所需木板的數量
第2到N+1行: 每行為一個整數，表示一塊木板的長度
輸出格式：一個整數，表示最少需要消耗的能量總和
輸入輸出樣例
輸入樣例#1：
3 8 5 8
輸出樣例#1：
34
說明
將長度為21的木板，第一次切割為長度為8和長度為13的，消耗21個單位的能量，第二次將長度為13的木板切割為長度為5和8的，消耗13個單位的能量，共消耗34個單位的能量，是消耗能量最小的方案。
?
小根堆
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #define lli long long int 7 using namespace std; 8 void read(lli & n) 9 { 10 char c='+';lli x=0;lli flag=0; 11 while(c<'0'||c>'9') 12 { 13 c=getchar(); 14 if(c=='-')flag=1; 15 } 16 17 while(c>='0'&&c<='9') 18 x=x*10+c-48,c=getchar(); 19 if(flag==1)n=-x; 20 else n=x; 21 } 22 priority_queue<lli,vector<lli>,greater<lli> >q; 23 lli n,p; 24 lli ans; 25 int main() 26 { 27 read(n); 28 for(int i=1;i<=n;i++) 29 { 30 read(p); 31 q.push(p); 32 } 33 for(int i=1;i<=n-1;i++) 34 { 35 lli x=q.top(); 36 q.pop(); 37 lli y=q.top(); 38 q.pop(); 39 x=x+y; 40 ans+=x; 41 q.push(x); 42 } 43 cout<<ans; 44 return 0; 45 }
?
