题目描述

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

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

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

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

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

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

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

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

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

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

样例

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

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

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

数据范围
n≤32767,ai≤106
输入样例：
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。

算法1

(暴力枚举)

借鉴隔壁大佬的题解

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int M=2e6;
bool vis[5000000];
int n,s,x,y,t;
int main() {
    scanf("%d%d%d",&n,&x,&y);
    n-=2;
    s=abs(y-x)+x;
    vis[y+M]=vis[x+M]=1;
    for(; n--; vis[x+M]=1) {
        scanf("%d",&x);
        t=0;
        for(;; t++) {
            if(vis[x+M-t]||vis[x+M+t]) {
                s+=t;
                break;
            }
        }
    }
    printf("%d", s);
    return 0;
}

算法2

(STL)

C++ 代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')
            w=-w;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        s=s*10+c-'0';
        c=getchar();
    }
    return s*w;
}
const int N=40000+5;
int n,ans;
set<int> s;
int main()
{
    n=read();
    s.insert(1e9);
    s.insert(-(1e9));
    ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        set<int>:: iterator it=s.lower_bound(x);
        if(i!=1)
            ans+=min(abs(x-*(--it)),abs(x-*it));
        else
            ans+=abs(x);
        s.insert(x);
    }
    printf("%d\n",ans);
    return 0;
}

算法3

(双向链表)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef pair<long long ,int > PII;
typedef long long LL;

int n;
PII a[N];
int l[N] , r[N];
int p[N];
PII ans[N];

int main(){

    cin >> n;

    for(int i = 1 ; i <= n ;i++)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
int an = 0;
an += a[1].first;
    sort(a + 1 , a + n + 1);
    a[0].first = -3e9, a[n + 1].first = 3e9;

    for(int i = 1 ; i <= n;i++)
    {
        l[i] = i - 1 , r[i] = i + 1;
        p[a[i].second] = i;
    }


    for(int i = n ; i > 1  ;i--)
    {
        LL temp = 0xcfcfcfcf;
        int ver = p[i] , left = l[ver] ,right = r[ver];
         temp = min(temp , abs(a[right].first - a[ver].first));
         temp = min(temp ,abs(a[left].first - a[ver].first));
        an += temp;
        l[right] =left , r[left] = right;
    }
   cout << an <<endl;
    return 0;
}

算法4

（手写Treap）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 32780 , INF = 0x3f3f3f3f;

struct Tree{
    int l,r;
    int val , key;
    int cnt;
}tr[N];

int n;
int tot , root;

int get_node(int x){
    tr[++tot].key = x;
    tr[tot].cnt = 1;
    tr[tot].val = rand();
    return tot; 
}

void pushup(int& p)
{
    tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt + tr[p].cnt;
}
void build()
{
    get_node(-INF),get_node(INF);
    root = 1,tr[1].r = 2;
}

void zap(int& p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p ,p = q;
    pushup(tr[p].l),pushup(p);
}
void zip(int& p){
    int q = tr[p].l;
    tr[p].l = tr[q].r , tr[q].r = p , p = q;
    pushup(tr[p].r),pushup(p);
}

void insert(int& p,int x){
    if(!p)p = get_node(x);
    if(tr[p].key == x)tr[p].cnt++;
    else if(x < tr[p].key)
    {
        insert(tr[p].l,x);
        if(tr[tr[p].l].val > tr[p].val)zip(p);
    }
    else {
        insert(tr[p].r , x);
        if(tr[tr[p].r].val > tr[p].val)zap(p);
    }
    pushup(p);
}

int get_prev(int& p ,int x)
{
    if(!p)return -INF;
    if(x < tr[p].key)return get_prev(tr[p].l , x);
    else return max(tr[p].key , get_prev(tr[p].r  ,x));
}

int get_next(int& p,int x)
{
    if(!p)return INF;
    if(x > tr[p].key)return get_next(tr[p].r,x);
    else return min(tr[p].key , get_next(tr[p].l , x));
}

int main(){
    build();
    cin >> n;
    int ans = 0;int x;
    for(int i = 1 ; i <= n ;i++)
    {
        cin >> x;
        if(i == 1)ans += x;
         else ans += min(x - get_prev(root, x), get_next(root, x) - x);


        insert(root , x);
    }
    cout << ans <<endl;
    return 0;
}