UVA11136 Hoax or what

题目描述

超市有n天的促销活动

每天有k张小票写着购物金额放入箱子中

这一天结束后就取出其中的最大值max和最小值min接着超市会放出max-min金额的奖品

问超市放出奖品金额的总价值是多少

样例

19
2

算法1

(multiset)

动态维护最大值和最小值我们可以用set和multiset
如果有多个相同的元素那么就必须使用multiset

时间复杂度 $O(NlongN)$

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define x first
#define y second

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
int n;

inline void solve()
{
    while(scanf("%d",&n) == 1)
    {
        if(n == 0) break;
        multiset<int> S;
        LL res = 0;
        for(int i = 0;i < n;i ++)
        {
            int k;
            scanf("%d",&k);
            for(int j = 0;j < k;j ++)
            {
                int x;
                scanf("%d",&x);
                S.insert(x);
            }
            set<int>::iterator fir,las;
            fir = S.begin();
            las = S.end();
            las --;
            res += *las - *fir;
            S.erase(las);
            S.erase(fir);
        }
        printf("%lld\n",res);
    }
}

int main()
{
    int _ = 1;
    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1);
    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

算法2

(deque + 排序)

我们可以用deque维护小票的集合
每次加入完新的小票后排序，取队首和队尾元素

时间复杂度 $O(NlongN)$

参考题解：(12条消息) UVA11136 Hoax or what【multiset+deque】_海岛Blog-CSDN博客

C++ 代码

看文献