python/TangDou/AcWing/BalanceTree/265.md

##[$AcWing$ $265$. 营业额统计](https://www.acwing.com/problem/content/267/)

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

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

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

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

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

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

$$\large f_i=\min_{1≤j<i}|a_i−a_j|$$

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

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

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

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

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

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

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

**数据范围**
$1≤n≤32767,|ai|≤10^6$

**输入样例**：

```cpp {.line-numbers}
6
5
1
2
5
4
6
```
**输出样例：**
```cpp {.line-numbers}
12
```

**样例解释**
在样例中，$5+|1−5|+|2−1|+|5−5|+|4−5|+|6−5|=5+4+1+0+1+1=12$。

### 二、$STL+SET$解法

老规矩，和我一起大声读，$STL$大法好！

```cpp {.line-numbers}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;

const int N = 40000 + 10;
int n, ans;

// AC 263 ms
set<int> s;
/*
注意事项
1.set中lower_bound返回的是迭代器it
2.为了防止lower_bound返回指针是set.end()–>即寻找不到,可以在set中预先加入两个哨兵
*/
int main() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;

    //加入哨兵是个好习惯，防止查找最小数前驱，或，最大数后继时，发生边界问题
    s.insert(-INF), s.insert(INF);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        auto it = s.lower_bound(x);

        if (i == 1) //第一天的最小波动值为第一天的营业额 a1
            ans += abs(x);
        else
            ans += min(abs(x - *(--it)), abs(x - *it));

        // x入set
        s.insert(x);
    }
    //输出结果
    printf("%d\n", ans);
    return 0;
}
```

### 三、题目解析
即要实现一个数据结构，可以实现插入，找离$x$最近的数这两个功能。后者可以转化为 **求前驱** 和 **后继** 的操作。可以用 **平衡树** 来实现，一个比较容易实现的版本是$Treap$。本题不需要记录$cnt$和$size$，直接当成每个数只出现一次就行了。