题解 | #营业额统计#

要求O(logN)插入或查找前驱后继，手搓平衡树或者STL自带的红黑树(map，set)都能做

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int N=2010,MOD=998244353,INF=0x7f7f7f7f;
// unordered_map<int,int>mp;
map<int,int>mp;


void solve(){
    int n;
    cin>>n;
    int x;
    cin>>x;
    int res=x;
    mp[INF]=mp[-INF]=1;
    mp[x]=1;
    while(--n){
        cin>>x;
        map<int,int>::iterator it=mp.find(x);
        if(it!=mp.end()){
            res+=0;
            mp[x]++;
        }else{
            mp[x]=1;
            it=mp.find(x);
            map<int,int>::iterator l=it,r=it;
            if(it!=mp.begin()) l--;
            if(it!=mp.end()) r++;
            res+=min(abs(x-l->first),abs(x-r->first) );
            // cout<<abs(x-l->first)<<' '<<abs(x-r->first) <<endl;
        }
    }
    cout<<res<<endl;
    
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0);

    int t;
    // cin>>t;
    t=1;
    while(t--) solve();
    
    return 0;
}