首页 > 代码库 > UVA - 11136Hoax or what(set)

UVA - 11136Hoax or what(set)

题目:UVA - 11136Hoax or what(set)


题目大意:超市举办一个活动,活动期间,凡是来到超市购物的客人将小票放到一个抽奖箱中,每天结束经理从中间抽出两张小票,一张最高的消费额,一张最低的消费额。然后最高消费的那位客人将获得max - min价值的商品。然后将这两张小票扔掉。活动期间都这么抽出幸运的顾客。问这个活动需要准备花多少钱在提供奖品上。


解题思路:用multiset来存放小票的金额,然后在取出最大和最小。


代码:

#include <cstdio>
#include <set>

using namespace std;

typedef long long ll;

multiset<int> s;
multiset<int>::iterator first, last;

int main () {

	int n, k, num;
	ll ans;
	while (scanf ("%d", &n) && n) {

		ans = 0;
		s.clear();
		while (n--) {
			
			scanf ("%d", &k);
			for (int i = 0; i < k; i++) {
				scanf ("%d", &num);
				s.insert (num);
			}
			first = s.begin();
			last = s.end();
			last--;
			
			ans += *last - *first; 
			s.erase(first);
			s.erase(last);
		}
		printf ("%lld\n", ans);
	}
	return 0;
}


UVA - 11136Hoax or what(set)