l*********y
发帖数: 142 | 1 第一次用multiset，不知道怎么用
题目应该很简单的，蛮力排序的话会超时。
网上的评论是
Easy. Don't use cin or cout and you could use a multiset :)
实在无语。没想出怎么用multiset。
谁给解释一下。谢谢了！
Problem H: Hoax or what
Each Mal-Wart supermarket has prepared a promotion scheme run by the
following
rules:
* A client who wants to participate in the promotion (aka a sucker) must
write down their phone number on the bill of their purchase and put the
bill into a special urn.
* Two bills are selected from the urn at the end of each day: first the
highest bill is selected and then the lowest bill is selected. The client
who paid the largest bill receives a monetary prize equal to the difference
between his bill and the lowest bill of the day.
* Both selected bills are not returned to the urn while all the
remaining ones are kept in the urn for the next day.
* Mal-Wart has many clients such that at the end of each day there are
at least two bills in the urn.
Your task is to write a program which takes information about the bills put
into the urn and computes Mal-Wart's cost of the promotion.
The input contains a number of cases. The first line in each case contains
an integer n, 1<=n<=5000, the number of days of the promotion. Each of the
subsequent n lines contains a sequence of non-negative integers separated by
whitespace. The numbers in the (i+1)-st line of a case give the data for
the i-th day. The first number in each of these lines, k, 0≤k≤105, is the
number of bill
s and the subsequent k numbers are positive integers of the bill amounts. No
bill is bigger than 106. The total number of all bills is no bigger than
106. The case when n = 0 terminates the input and should not be processed.
For each case of input print one number: the total amount paid to the
clients by Mal-Wart as the result of the promotion.
Sample input
5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2
2
2 1 2
2 1 2
0
Output for sample input
19
2 |
c****p
发帖数: 6474 | 2 用一个最大堆和最小堆就可以了吧。。
或者直接BST也可以。
【在 l*********y 的大作中提到】
: 第一次用multiset，不知道怎么用
: 题目应该很简单的，蛮力排序的话会超时。
: 网上的评论是
: Easy. Don't use cin or cout and you could use a multiset :)
: 实在无语。没想出怎么用multiset。
: 谁给解释一下。谢谢了！
: Problem H: Hoax or what
: Each Mal-Wart supermarket has prepared a promotion scheme run by the
: following
: rules:
|
l*********y
发帖数: 142 | 3 是可以，但是如果你在最大堆拿掉一个最大值，同时也要拿掉最小堆的这个值。
这样就要implement heap.find，而不能用STL 的 priority_queue了，因为priority_
queue里没有find。
这样编程很累的。我看很多人谈论这道题都是说multiset,所以来问一下。
多谢了
【在 c****p 的大作中提到】
: 用一个最大堆和最小堆就可以了吧。。
: 或者直接BST也可以。
|
c****p
发帖数: 6474 | 4 multiset的数据是ordered。
所以 begin()返回最小值的iterator，end()-1返回最大值的iterator，
然后erase()就可以了。
本质上还是某种二叉搜索树。
【在 l*********y 的大作中提到】
: 是可以，但是如果你在最大堆拿掉一个最大值，同时也要拿掉最小堆的这个值。
: 这样就要implement heap.find，而不能用STL 的 priority_queue了，因为priority_
: queue里没有find。
: 这样编程很累的。我看很多人谈论这道题都是说multiset,所以来问一下。
: 多谢了
|
h**6
发帖数: 4160 | 5 multiset和set的用法完全一样，只是允许有多个数重复而已。每天向multiset里insert一行数值，并把最大和最小的去掉即可。 |
