首页 > 代码库 > 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;
}