直接用c++的set
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n ;
set<pair<int,int>> s ;
int main()
{
cin >> n ;
s.insert({-2e9, 0}); // 加入哨兵方便判断边界
s.insert({2e9, 0});
long long res = 0 ;
for(int i = 1 ; i <= n ;i ++)
{
int v ;
cin >> v ;
if(i == 1) res += v ;
if(i > 1)
{
auto maxs = s.lower_bound({v,0}); // 用二分找到第一个大于等于v的下标
auto mins = maxs ;
mins -- ; // 下标-1即是小于x的第一个数
ll ans1 = v - mins -> first ;
ll ans2 = maxs -> first - v ;
if(ans1 <= ans2) res += ans1 ;
else res += ans2 ;
}
s.insert({v,i});
}
cout << res << endl;
return 0;
}