python/TangDou/AcWing/BalanceTree/265_Vector.cpp

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
/*
其实跟 普通平衡树 使用vector方法差不多，只是要注意先插入一个-INF和INF的数用来防止使用lower_bound和upper_bound的时候越界。
*/
// 727 ms
vector<int> a;

int main() {
    int n;
    cin >> n;

    a.push_back(-INF), a.push_back(INF);

    //首次插入
    int x;

    int res = 0;

    //后续插入
    for (int i = 1; i <= n; i++) {
        cin >> x;

        if (i == 1)
            res += x;
        else {
            int prev = lower_bound(a.begin(), a.end(), x) - a.begin();
            if (a[prev] != x) prev = lower_bound(a.begin(), a.end(), x) - a.begin() - 1;
            //如果序列之中没有等于当前的数，那我们取严格小于当前的数

            int next = upper_bound(a.begin(), a.end(), x) - a.begin(); //后继

            //按题目要求来计算
            res += min(abs(x - a[prev]), abs(a[next] - x));
        }
        //将x放入vector中
        a.insert(lower_bound(a.begin(), a.end(), x), x);
    }
    //输出
    printf("%d\n", res);
    return 0;
}