[UVA][multiset使用] 11136 - Hoax or what
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.
- It is quite obvious why Mal-Wart is doing this: they sell crappy products which break quickly and irreparably. They give a short-term warranty on their products but in order to obtain a warranty replacement you need the bill of sale. So if you are gullible enough to participate in the promotion you will regret it.
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 bills 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
T. Walen, adapted by P. Rudnicki
題目不難，對於每天一天納入所有價錢，每次查詢最大值與最小值，並把這兩個值從集合中移去。
這裡使用 multiset，
有幾點要注意，要 erase 其中一個元素時，倘若使用傳值進去，則會將所有同值的都刪除，若傳入位址，就只會刪除當前那一個。
秒速很聳動 0.864 s
#include <stdio.h>
#include <set>
using namespace std;
int main() {
int n, m, x, i, tmp;
while(scanf("%d", &n) == 1 && n) {
multiset<int> S;
multiset<int>::iterator it, kt;
multiset<int>::reverse_iterator jt;
long long sum = 0;
for(i = 0; i < n; i++) {
scanf("%d", &m);
while(m--) {
scanf("%d", &x);
S.insert(x);
}
it = S.begin(), jt = S.rbegin();
sum += *jt - *it;
S.erase(it);
S.erase(S.find(*jt));
m = 2*(n-i+1);
if(S.size() > m) {
tmp = n-i+1;
while(tmp) it++, tmp--;
tmp = n-i+1, kt = S.end();
while(tmp) kt--, tmp--;
S.erase(it, kt);
}
}
printf("%lld\n", sum);
}
return 0;
}