UVa 11136 - Hoax or What(可重集)

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

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

要注意数据量大,用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博客 ,格式可能有所偏差。

支付宝扫码领红包