机器狗组装费用
时间限制(普通/Java):1500 MS/ 4500 MS运行内存限制 : 65536 KByte总提交 : 490测试通过 : 166
题目描述
sed同学最近迷上了制造机器狗，购置了大量所需零件，零件可以组装为一个组件，这些组件或零件又可以组装为一个大的组件。在制造机器狗中，组件或零件只能两两进行组装，组装的顺序任意。在机器狗中，每个零件都有一个组装成本，每次组装一个组件的费用为各个零件组装成本之和。给定各个零件组装成本（单位为元），你的任务是帮助sed计算他至少花费多少费用。
输入
第一行包括一个整数N，表示机器狗零件数(1≤N≤10000)
第二行为N个正整数，表示每个机器狗零件组装成本（单位为元），整数之间用空格隔开。
输出
输出仅一行，即机器狗组装的最少费用。
注意：输出部分的结尾要求包含一个多余的空行。
样例输入
10
1234567890
样例输出
136
题目来源
“IBM南邮杯”个人赛
题目链接：http://acm./acmhome/problemdetail.do?&method=showdetail&id=1076
题目分析：裸优先权队列，优先权为从小到大，每次取最小的两个出队相加累计并把和入队，直到队列中只有一个元素
#include <cstdio>#include <queue>using namespace std;int const MAX = 1e5 + 5;struct cmp{bool operator()(int a, int b){return a > b;}};priority_queue <int, vector<int>, cmp> q;int main(){int n, get;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &get);q.push(get);}int ans = 0;while(q.size() != 1){int tmp1 = q.top();q.pop();int tmp2 = q.top();q.pop(); int tmp = tmp1 + tmp2;ans += tmp;q.push(tmp);}printf("%d\n", ans);}
