机器狗组装费用
时间限制(普通/Java):1500 MS/4500 MS 运行内存限制 : 65536 KByte总提交 : 491测试通过 : 167
题目描述
sed同学最近迷上了制造机器狗，购置了大量所需零件，零件可以组装为一个组件，这些组件或零件又可以组装为一个大的组件。在制造机器狗中，组件或零件只能两两进行组装，组装的顺序任意。在机器狗中，每个零件都有一个组装成本，每次组装一个组件的费用为各个零件组装成本之和。给定各个零件组装成本（单位为元），你的任务是帮助sed计算他至少花费多少费用。
输入
第一行包括一个整数N，表示机器狗零件数(1≤N≤10000)
第二行为N个正整数，表示每个机器狗零件组装成本（单位为元），整数之间用空格隔开。
输出
输出仅一行，即机器狗组装的最少费用。
注意：输出部分的结尾要求包含一个多余的空行。
样例输入
10
1234567890
样例输出
136
解题思路：要求组装费用最小，每次两个价值最小的相加，再加入总费用中即可，典型优先队列，优先队列默认值大的优先极高，可通过cmp修改优先权。
代码如下：
#include <cstdio>#include <queue>using namespace std;struct cmp{bool operator ()(int &a,int &b){return a>b; //值小优先级高}};int main(){priority_queue <int ,vector<int>,cmp> q;int x,n,i,ans=0;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&x);q.push(x);}while(q.size()>1){int t=q.top();q.pop();t+=q.top();q.pop();ans+=t;q.push(t);}printf("%d\n", ans);return 0;}
