UVa 11136

X-Plosives

from Chapter 3. Data Structures :: Fundamental Data Structures :: Exercises: Beginner

Problem

超市举办一个活动，要求每个顾客在小票上签字后放入一个箱子中。每天，工作人员从箱子里取出金额最大的和金额最小的两张小票，金额最大的小票对应的顾客将得到价值等同于两张小票金额差值的礼品。之后，这两张小票便丢掉，不再放入箱子中，而其他小票依然留在箱中。

（1 ≤ 活动天数 ≤ 5000，小票总数不超过10^6）

Solution

题目有提示使用STL可能不能AC，但是这道题目前无法提交，无法知道实际的情况，所以在这也仅仅只是讲一下我的解题思路。

利用STL中的multiset模拟整个过程即可，由于multiset的底层是红黑树，所以可以很方便的insert和earse最大值和最小值。不过由于红黑树时间复杂度的常数略大，因此不知道能不能解决这道题目。（听闻有用最大-最小堆来解决这道题的，应该在时间的表现上会更加优秀。）

该算法的时间复杂度为 O(N·logN) 。