问一道multiset的题# JobHunting - 待字闺中
l*y
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
题目应该很简单的，蛮力排序的话会超时。
网上的评论是
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
