UVa 11136 - Hoax or what（可重集）

发表于 分类于 ， ， Disqus：

超市促销活动，每天从箱子里把最大和最小的小票拿出来，送出等于其差值的奖金，求送出的总和。

使用可重集本身就是有序排列，不会超时每次从中取出头尾两个元素求差的和。

要注意数据量大，用cin、cout要关闭流同步，还有求和应该使用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
#include<iostream>
#include<set>
using namespace std;
multiset<int> a;
int main(){
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n){
        long long sum=0;
        a.clear();
        while(n--){
            int m,k;
            cin>>m;
            while(m--){
                cin>>k;
                a.insert(k);
            }
            multiset<int>::iterator it1=a.begin(),it2=--a.end();
            sum+=*it2-*it1;
            a.erase(it1);
            a.erase(it2);
        }
        cout<<sum<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **