[HNOI 2002] 营业额统计

知识点

有序集合、前驱后继、最邻近查询

解题思路

用有序集合保存此前营业额。第一天直接计入当天值（可能为负）；以后用lower_bound找到不小于当前值的最小历史数，并与其前驱比较距离，取较小差值累加，再插入当前值。

正确性说明

已排序数列中，任何比前驱更小或比后继更大的数都离当前值更远，所以最小绝对差一定由这两个邻居提供。重复值距离为0。逐日先查询后插入确保只与过去比较，首日按特殊定义计入。

易错点

营业额可以为负，首日不能取绝对值；后继可能不存在，前驱可能不存在；总和使用64位。

复杂度

时间O(n log n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;set<long long>s;long long ans=0;for(int i=0;i<n;i++){long long x;cin>>x;if(i==0)ans+=x;else{auto it=s.lower_bound(x);long long best=LLONG_MAX;if(it!=s.end())best=min(best,abs(*it-x));if(it!=s.begin())best=min(best,abs(*prev(it)-x));ans+=best;}s.insert(x);}cout<<ans<<'\n';}