Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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.

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≤10⁵, is the number of bills and the subsequent k numbers are positive integers of the bill amounts. No bill is bigger than 10⁶. The total number of all bills is no bigger than 10⁶. 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;
}