洛谷 - P2234 [HNOI2002]营业额统计

题面

难度：提高+/省选-
标签：SBT Splay 概率论,统计 各省省选 湖南 2002

题目描述

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

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

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

$\text{该天的最小波动值}=\min(|\text{该天以前某一天的营业额} - \text{该天营业额}|)$ 。

输入格式

第一行为正整数 $n$（$n \leq 32767$） ，表示该公司从成立一直到现在的天数，接下来的 $n$ 行每行有一个整数 $a_i$ ($|a_i| \leq 1000000$) ，表示第 $i$ 天公司的营业额，可能存在负数。

输出格式

一个正整数，表示 $\sum{\text{每一天的最小波动值}}$ ，数据保证结果小于 $2^{31}$ 。

输入输出样例

输入样例 #1

6
5
1
2
5
4
6

输出样例 #1

12

样例说明 #1

$$\begin{aligned} &\ 5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|\\ =&\ 5+4+1+0+1+1\\ =&\ 12 \end{aligned}$$

思路

由 $\text{该天的最小波动值} = \min(|\text{该天以前某一天的营业额} - \text{该天营业额}|)$ 可以判断出当前波动值与前面有关，设当天营业额为 $x$ ，则需要查找到某一天营业额 $y$ 满足 $|y-x|$ 最小。

接着想到二分查找，使用 STL 库函数 lower_bound 和 upper_bound 即可完成。 二分查找需要保证数组有序，所以边读入边处理既能保证数组有序，又可以简单地查询出该天的最小波动值。

为了防止越界，开始前先向 a 中 push_back 一个满足要求的"极小值" $-1061109568$ 。

时间复杂度： $O(n \log_2 n)$ 。

代码

提交详情：R44587104

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x, sum = 0;
    vector<int> a;
    cin >> n >> x;
    a.push_back(0xc0c0c0c0);
    a.push_back(x);
    sum += x;
    for (int i = 2; i <= n; i++) {
        cin >> x;
        int t1 = *--lower_bound(a.begin(), a.end(), x);
        int t2 = *lower_bound(a.begin(), a.end(), x);
        if (t1 == 0xc0c0c0c0) {
            sum += abs(t2 - x);
        } else {
            sum += min(abs(t1 - x), abs(t2 - x));
        }
        a.insert(upper_bound(a.begin(), a.end(), x), x);
    }
    cout << sum << endl;
    return 0;
}

参考资料

1. std::lower_bound - cppreference
2. std::upper_bound - cppreference