STL 的算法的时间复杂度还是可以的

#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int main()
{
    int n; cin >> n;
    int sum; cin>> sum;
    a.push_back(sum);
    for(int i = 1,v; i < n; ++i)
    {
        scanf("%d",&v); a.insert(lower_bound(a.begin(),a.end(),v),v);
        int pos = lower_bound(a.begin(),a.end(),v)-a.begin();
        if(pos == 0) sum += abs(v-a[pos+1]);
        else if(pos == a.size()) sum += abs(v-a[pos-1]);
        else sum += min(abs(v-a[pos-1]),abs(v-a[pos+1]));
    }
    cout << sum;
}