AcWing 265. 营业额统计(用set实现)
原题链接
简单
作者:
负壹
,
2021-01-29 22:53:36
,
所有人可见
,
阅读 466
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
int n;
int main()
{
scanf("%d", &n);
set<int>st;
LL res = 0;
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (i == 1) res += x;
else {
int a,b;
auto it = st.lower_bound(x);
if(it!=st.end())a = *it;
else a = 1e9;
if(it!=st.begin())b = *(--it);
else b = -1e9;
res += min(a-x,x-b);
}
st.insert(x);
}
printf("%lld\n", res);
return 0;
}