题目描述

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

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

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

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

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

设第i天的营业额为aiai,则第i天(i≥2i≥2)的最小波动值fifi被定义为：

fi=min1≤j<i|ai−aj|
fi=min1≤j<i|ai−aj|
当最小波动值越大时，就说明营业情况越不稳定。

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

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

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

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

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

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

数据范围
n≤32767,ai≤106

样例

输入样例：
6
5
1
2
5
4
6
输出样例：
12

STL

(set + 桶) $O(nlogn)$

将数据存入set中用正桶和负桶两个桶来维护重复数据（set支持重复插入功能但我把函数忘了，要不然count是干什么的呢？）

如果数据出现过则直接跳过操作，否则用迭代器找出输入数据的前驱和后继（具体细节看代码），最后计算即可

时间复杂度分析：输入循环$O(n)$set$O(logn)$总复杂度$O(nlogn)$

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
using namespace std;
#include<set>
const int N = 40001;
const int M = 1e6 + 1;
const int inf = 0x3f3f3f3f;
int f[N];
int t_z[M];
int t_f[M];
set<int> a;
inline int read()
{
    char c;
    int flag = 1;
    while ((c = getchar()) < '0' || c > '9')
    {
        if (c == '-')
        {
            flag = -1;
        }
    }
    int count = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
    {
        count = count * 10 + c - '0';
    }
    return count * flag;
}
int main()
{
    set<int>::iterator it;
    int n = read();
    for (register int i = 1; i <= n; i++)
    {
        int x = read();
        int h = inf;
        int q = inf;
        if (x >= 0)
        {
            if (t_z[x] == 1)
            {
                continue;
            }
        }
        else
        {
            if (t_f[-x] == 1)
            {
                continue;
            }
        }
        a.insert(x);
        it = a.find(x);
        it++;
        if (it != a.end()) { h = *it; }
        it--;
        if (it != a.begin()) { it--; q = *it; }
        if(i == 1) f[i] = x;
        if (h != inf || q != inf)f[i] = min(abs(x - h), abs(x - q));
        if (x >= 0)
        {
            t_z[x] = 1;
        }
        else
        {
            t_f[-x] = 1;
        }
    //  printf("f[i] = %d h = %d q = %d\n", f[i], h, q);
    }
    long long count = 0;
    for (register int i = 1; i <= n; i++)
    {
        count += f[i];
    }
    cout << count;
    return 0;
}