andyli

题解 UVA11136 【Hoax or what】
本题可以利用$STL$来简化代码,题目中的操作可以用$multiset$来模拟,$max$对应的是$s.$rbeg...
扫描右侧二维码阅读全文
22
2019/07

题解 UVA11136 【Hoax or what】

本题可以利用$STL$来简化代码,题目中的操作可以用$multiset$来模拟,$max$对应的是$s.$rbegin$()$,$min$对应的是$*s.begin()$,扔掉对应的是$s.erase(s.find(^*s.rbegin())), s.erase(s.find(^*s.begin()))$。
本题也可以手写小根堆和大根堆进行模拟。
代码如下:

#include <cstdio>
#include <set>
using namespace std;

int main()
{
    int n;
    while (~scanf("%d", &n) && n) {
        long long ans = 0;
        multiset<int> s;
        for (int i = 1; i <= n; i++) {
            int k;
            scanf("%d", &k);
            for (int j = 1; j <= k; j++) {
                int x;
                scanf("%d", &x);
                s.insert(x);
            }
            int Mx = *s.rbegin(), Mn = *s.begin();
            ans += Mx - Mn;
            s.erase(s.find(Mx));
            s.erase(s.find(Mn));
        }
        printf("%lld\n", ans);
    }
    return 0;
}
Last modification:November 6th, 2019 at 05:09 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment