紫书p244
有n个数的集合s,每次可以从s中删除两个数,然后把他们的和放回集合,直到只剩下一个数。每次操作的开销等于删除两个数之和,求最小开销。所有书均小于e5。
此题等价于合并操场上的一堆石堆,求花费最少的力气是多少?
贪心最简单的问题。
关键的优先的队列的应用
priority_queue<int, vector<int>, greater<int> > q;
代码如下:
#include <iostream>
#include <queue>
using namespace std;
int n, x;
int main(){
while(cin >> n && n){
priority_queue<int, vector<int>, greater<int> > q;
for(int i = 0; i < n; i++) { cin >> x; q.push(x);}
int ans = 0;
for(int i = 0; i < n - 1; ++i){
int a = q.top(); q.pop();
int b = q.top(); q.pop();
ans += a + b;
}
cout << ans <<endl;
}
return 0;
}