<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。

分析营业情况是一项相当复杂的工作。

由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。

经济管理学上定义了一种最小波动值来衡量这种情况。

设第 $i$ 天的营业额为 $a_i$，则第 $i$ 天($i \\ge 2$)的最小波动值 $f_i$ 被定义为：

$f_i=min_{1 \\le j < i}|a_i-a_j|$

当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。

你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

第一天的最小波动值为第一天的营业额 $a_1$。

输入格式

第一行为正整数 $n$，表示该公司从成立一直到现在的天数。

接下来的 $n$ 行每行有一个整数 $a_i$(有可能有负数) ，表示第 $i$ 天公司的营业额。

输出格式

输出一个正整数，表示最小波动值的和。

数据范围

$1 \\le n \\le 32767, |a_i| \\le 10^6$

输入样例：

6
5
1
2
5
4
6

输出样例：

12

样例解释

在样例中，$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$。

思路

不懂$Treap$的可以看下我的分享
这道题就是把当前天之前的所有数都加到平衡树当中，然后每次累加与前继和后继的差的最小资累加起来即可。

代码

#include <iostream>
#include <cstdlib>
using namespace std;
const int N = 40010,INF = 1e7;
int n;
struct treap_node {
    int l,r;
    int key,val;
    int size,cnt;
}tr[N];
int root,idx;
int new_node (int key) {
    tr[++idx].key = key,tr[idx].val = rand (),tr[idx].cnt = tr[idx].size = 1;
    return idx;
}
void push_up (int u) {
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}
void left_rotate (int &u) {
    int p = tr[u].r;
    tr[u].r = tr[p].l,tr[p].l = u,u = p;
    push_up (tr[u].l),push_up (u);
}
void right_rotate (int &u) {
    int p = tr[u].l;
    tr[u].l = tr[p].r,tr[p].r = u,u = p;
    push_up (tr[u].r),push_up (u);
}
void init () {
    new_node (-INF),new_node (INF);
    root = 1,tr[root].r = 2;
    if (tr[root].val < tr[tr[root].r].val) left_rotate (root);
}
void insert (int &u,int key) {
    if (!u) u = new_node (key);
    else if (tr[u].key == key) tr[u].cnt++;
    else if (tr[u].key > key) {
        insert (tr[u].l,key);
        if (tr[tr[u].l].val > tr[u].val) right_rotate (u);
    }
    else {
        insert (tr[u].r,key);
        if (tr[tr[u].r].val > tr[u].val) left_rotate (u);
    }
    push_up (u);
}
int get_prev (int u,int key) {
    if (!u) return -INF;
    if (tr[u].key > key) return get_prev (tr[u].l,key);
    return max (tr[u].key,get_prev (tr[u].r,key));
}
int get_next (int u,int key) {
    if (!u) return INF;
    if (tr[u].key < key) return get_next (tr[u].r,key);
    return min (tr[u].key,get_next (tr[u].l,key));
}
int main () {
    init ();
    cin >> n;
    int ans;
    cin >> ans;
    insert (root,ans);
    for (int i = 2;i <= n;i++) {
        int x;
        cin >> x;
        ans += min (abs (x - get_prev (root,x)),abs (x - get_next (root,x)));
//      cout << x << ' ' << get_prev (root,x) << endl;
//      puts ("----------");
        insert (root,x);
    }
    cout << ans << endl;
    return 0;
}