題目： UVa - 11136 - Hoax or what

題目說明

超市進行促銷，把帳單放入一個箱子中，每天會放入一些帳單，接著取出金額最大及最小的帳單，並且支付 最大 - 最小 的金額，求 n 天後總共需要支付多少錢。

Input： 每組測資起始於一個整數 n，代表接下來有 n 行資料代表放入的帳單，若 n 為 0 代表結束，每行資料起始於一個整數 num，表示今天有 num 筆帳單要放入，中間以空格隔開。

Output： 輸出每組測資經過 n 天後總共需要支付多少錢。

解題思路

使用 Multiset 儲存帳單，接著每天從頭跟尾取出資料即可。使用 Multiset 的原因是可能會有兩張相同金額的帳單。需要注意的是因為測資的大小，所以結果使用 long long 儲存。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <set>

using namespace std;

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

int main()
{
    int n;
    while (cin >> n && n)
    {
        long long ret = 0;
        multiset<int> s;
        for (int i = 0; i < n; ++i)
        {
            int num, tmp;
            cin >> num;
            for(int j = 0; j < num; ++j) cin >> tmp, s.insert(tmp);
            auto l = s.begin(), r = --s.end();
            ret += *r - *l;
            s.erase(l), s.erase(r);
        }
        cout << ret << '\n';
    }
}