uva10954 - Add All(multiset函数)

本文主要是介绍uva10954 - Add All(multiset函数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：10954 - Add All

题目大意：求n个数的和，但是有点不一样的是题目要求计算最少花费。每次两个数相加，得到的那个数就是每次计算的cost。

解题思路：之前没有想到用multiset，自己写好麻烦。要求cost 最小的话，说明每次都将这些数里面最小的两个做相加，这样每次花费都是最小的。用multiset，就可以将每次计算的结果插入这些已经有序的数据中相应的位置，使得这个序列依旧有序。

代码：

#include <stdio.h>
#include <set>
using namespace std;int n;
multiset<int> num;long long solve () {long long sum = 0;multiset<int>::iterator it1, it2;long long temp;while (1) {if (num.size() == 1)break;it1 = num.begin();it2 = it1++;temp = *it1 + *it2;sum += temp;num.erase(it1);num.erase(it2);num.insert(temp);}return sum;
}int main () {int temp;while (scanf ("%d", &n), n) {num.clear();for (int i = 0; i < n; i++) {scanf ("%lld", &temp);num.insert (temp);}printf ("%lld\n", solve());}return 0;
}

这篇关于uva10954 - Add All(multiset函数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---