营业额统计

题目描述

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

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

最小波动值定义

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

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

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

问题

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例

6
5
1
2
5
4
6

输出样例

12

样例解释

天数	营业额	最小波动值计算	值
1	5	$a_1$	5
2	1	$\min|1-5|$	4
3	2	$\min|2-5|, |2-1|$	1
4	5	$\min|5-5|, |5-1|, |5-2|$	0
5	4	$\min|4-5|, |4-1|, |4-2|, |4-5|$	1
6		$\min|6-5|, |6-1|, |6-2|, |6-5|, |6-4|$

总和：$5 + 4 + 1 + 0 + 1 + 1 = 12$

问题分析

对于第 $i$ 天的营业额 $a_i$，我们需要在前面 $i-1$ 天的营业额中找到与 $a_i$ 最接近的值，即：

• 小于等于 $a_i$ 的最大值（前驱）
• 大于等于 $a_i$ 的最小值（后继）

然后 $f_i$ 就是 $a_i$ 与这两个值中差值较小的那个：

$$f_i = \min(|a_i - \text{predecessor}|, |a_i - \text{successor}|)$$

数据结构选择

我们需要一个数据结构支持：

1. 插入一个数
2. 查询一个数的前驱和后继

平衡二叉搜索树可以高效地支持这些操作：

• 插入：$O(\log n)$
• 查询前驱/后继：$O(\log n)$

可用数据结构

1. C++ STL set：基于红黑树，可以轻松查找前驱和后继
2. 手写平衡树：如AVL树、Treap、Splay树等
3. 离散化+树状数组/线段树：但需要处理负数

算法步骤

1. 初始化总和 $sum = a_1$
2. 将 $a_1$ 插入平衡树
3. 对于 $i = 2$ 到 $n$：
   • 在平衡树中查找 $a_i$ 的前驱和后继
   • 计算 $f_i = \min(|a_i - \text{predecessor}|, |a_i - \text{successor}|)$
   • 将 $f_i$ 加到 $sum$ 中
   • 将 $a_i$ 插入平衡树
4. 输出 $sum$

C++ STL set 实现

使用 set 的 lower_bound 和 upper_bound 函数：

• lower_bound(x)：返回第一个大于等于 x 的元素的迭代器
• upper_bound(x)：返回第一个大于 x 的元素的迭代器
• 前驱 = lower_bound(x) 的前一个元素
• 后继 = lower_bound(x) 或 upper_bound(x)（如果 lower_bound 找到的就是 x 本身）

#include <iostream>
#include <set>
#include <cmath>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    set<int> s;
    int x;
    cin >> x;
    s.insert(x);
    long long sum = x;  // 第一天的最小波动值就是第一天的营业额
    
    for (int i = 2; i <= n; i++) {
        cin >> x;
        
        auto it = s.lower_bound(x);  // 找到第一个大于等于x的元素
        
        int min_diff = INT_MAX;
        
        // 检查后继
        if (it != s.end()) {
            min_diff = min(min_diff, abs(x - *it));
        }
        
        // 检查前驱
        if (it != s.begin()) {
            it--;  // 前一个元素就是前驱
            min_diff = min(min_diff, abs(x - *it));
        }
        
        sum += min_diff;
        s.insert(x);
    }
    
    cout << sum << endl;
    return 0;
}

处理边界情况

1. 第一天：最小波动值就是 $a_1$
2. 没有前驱或后继：只计算存在的那个
3. 有重复营业额：如果找到相等的值，差值为0

时间复杂度

• 每次插入：$O(\log n)$
• 每次查询前驱/后继：$O(\log n)$
• 总时间复杂度：$O(n \log n)$
• 对于 $n \le 32767$，完全可行

示例详细计算

输入样例计算过程

第一天： $a_1 = 5$

• 插入5到set
• $sum = 5$

第二天： $a_2 = 1$

• set: {5}
• 查找1的前驱和后继：
  • 后继：lower_bound(1) 找到5
  • 前驱：begin()，没有前驱
• $f_2 = \min(|1-5|) = 4$
• $sum = 5 + 4 = 9$
• 插入1

第三天： $a_3 = 2$

• set: {1, 5}
• 查找2的前驱和后继：
  • 后继：lower_bound(2) 找到5
  • 前驱：1
• $f_3 = \min(|2-5|=3, |2-1|=1) = 1$
• $sum = 9 + 1 = 10$
• 插入2

第四天： $a_4 = 5$

• set: {1, 2, 5}
• 查找5的前驱和后继：
  • lower_bound(5) 找到5（自身）
  • 前驱：2
• $f_4 = \min(|5-5|=0, |5-2|=3) = 0$
• $sum = 10 + 0 = 10$
• 插入5（但5已存在，set中仍然只有一个5）

第五天： $a_5 = 4$

• set: {1, 2, 5}
• 查找4的前驱和后继：
  • 后继：5
  • 前驱：2
• $f_5 = \min(|4-5|=1, |4-2|=2) = 1$
• $sum = 10 + 1 = 11$
• 插入4

第六天： $a_6 = 6$

• set: {1, 2, 4, 5}
• 查找6的前驱和后继：
  • 后继：end()，没有后继
  • 前驱：5
• $f_6 = \min(|6-5|=1) = 1$
• $sum = 11 + 1 = 12$

输出： 12

注意事项

1. 整数范围：$|a_i| \le 10^6$，使用 int 类型足够
2. 总和范围：最坏情况下，每天波动值最大约 $2 \times 10^6$，$n=32767$，总和最大约 $6.5 \times 10^{10}$，需要使用 long long
3. 平衡树选择：C++ STL set 足够高效
4. 重复元素：set 自动去重，不影响结果（因为相同营业额差值为0）

扩展：手写平衡树

如果不用STL，可以手写Treap或Splay树：

struct Node {
    int key;
    int priority;
    Node *left, *right;
    
    Node(int k) : key(k), priority(rand()), left(nullptr), right(nullptr) {}
};

// 插入、查找前驱后继等操作

时空限制

• 时间限制：1秒
• 空间限制：64MB

对于 $n=32767$，$O(n \log n)$ 算法完全可以在1秒内完成。