P2234 [HNOI2002]营业额统计

#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
set<int> s;
set<int>::iterator iter, before;
int main()
{
	scanf("%d", &n);
	scanf("%d", &x);
	s.insert(x);
	ans+=x; 
	for(int i=2; i<=n; ++i){
		scanf("%d", &x);
		//找到第一个大于等于x的位置 
		iter=s.lower_bound(x);
		//x在里面是最小的 
		if(iter==s.begin()){	
			ans+=abs(*iter-x);
		}
		else{
            before=iter;
            before--;
			ans+=min(abs(x-*iter), abs(x-*before));
		}
		s.insert(x);
	}
	printf("%d", ans);
	return 0;
}

或者

#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
set<int> s;
set<int>::iterator iter, before;
int main()
{
	scanf("%d", &n);
	s.insert(1e9);
	s.insert(-1e9);
	for(int i=1; i<=n; ++i){
		scanf("%d", &x);
		if(i==1){	
			ans+=x;
		}
		else{
			iter=s.lower_bound(x); 
			before=iter;
			before--;
			ans+=min(abs(x-*iter), abs(x-*before));
		}
		s.insert(x);
	}
	printf("%d", ans);
	return 0;
}