洛谷P2234 [HNOI2002]营业额统计

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<set>
 5 using namespace std;
 6 typedef long long LL;
 7 typedef set<LL>::iterator setit;
 8 const LL INF=0x3f3f3f3f3f3f3f3f;
 9 int n;
10 LL ans;
11 set<LL> s;
12 int main(){
13     scanf("%d",&n);
14     scanf("%lld",&ans);s.insert(ans); 
15     for(int i=1;i<n;++i){
16         LL tmp,x=INF,y=INF;
17         scanf("%lld",&tmp);
18         if(s.find(tmp)!=s.end()) continue;//已存在相同的数 
19         setit it=s.upper_bound(tmp);
20         if(it!=s.end()) x=abs(*it-tmp);//若能找到不小于它的数 求出两数之差 
21         if(it!=s.begin()) y=abs(*(--it)-tmp);//若能找到不大于它的数 求出两数之差 
22         ans+=min(x,y);//比较两个差值的大小 
23         s.insert(tmp);//插入该数 
24     }
25     printf("%lld",ans);
26     return 0;
27 }