方法1：平衡树

直接利用平衡树的前驱和后驱求解答案
此方法来自： 菜鸡的我自己打的

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,a;
LL ch[100005][4];
LL val[100005];
LL rot,tot,ans;
void add(LL x)
{
    LL u=rot,fa=0;
    while(u&&val[u]!=x){
        fa=u;
        u=ch[u][x>val[u]];
    }
    if(!u){
        u=++tot;
        if(!fa) rot=u;
        else ch[fa][x>val[fa]]=u;
        val[u]=x;
    }
}
LL qq(LL x)//前驱 
{
    LL u=rot,ans=-3000000;
    while(1)
    {
        if(val[u]<=x)   
            ans=val[u];
        if(ch[u][0]&&val[u]>x)
            u=ch[u][0];
        else if(ch[u][1]&&val[u]<x)
            u=ch[u][1];
        else
            return ans;
    }
}
LL hq(LL x)//后驱 
{
    LL u=rot,ans=3000000;
    while(1)
    {
        if(val[u]>=x)   
            ans=val[u];
        if(ch[u][0]&&val[u]>x)
            u=ch[u][0];
        else if(ch[u][1]&&val[u]<x)
            u=ch[u][1];
        else
            return ans;
    }
}
LL find(LL x)
{
    return min(x-qq(x),hq(x)-x);
}

LL ll[100005],big;
void dfs(LL x)
{
    if(ch[x][0]) dfs(ch[x][0]);
        ll[++big]=x;
    if(ch[x][1]) dfs(ch[x][1]);
}
void phto(LL &fa,LL l,LL r)
{
    LL mid=(l+r)/2;
    fa=ll[mid];
    if(l<mid)
        phto(ch[ll[mid]][0],l,mid-1);
    if(r>mid)
        phto(ch[ll[mid]][1],mid+1,r);
}
void ph()//重新平衡 
{
    big=0;
    dfs(rot);
    memset(ch,0,sizeof(ch));
    phto(rot,1,big);
}

int main()
{
//  freopen("money.in","r",stdin);
//  freopen("money.out","w",stdout);
    cin>>n;
    while(n--)
    {
        scanf("%lld",&a);
        ans+=find(a);
        add(a);
        if(clock()>200&&n%500==0)
            ph();
    }
    cout<<ans<<endl;
    return 0;
}

方法2：调用STL

众所周知，set能有序地维护同一类型的元素，但相同的元素只能出现一次。
对于这道题来说，我们可以用set来记录下之前出现过的所有营业额。
每次输入一个新的数x后，通过lowerbound操作找到set中大于等于x的第一个数。
0.如果这是第一个数，直接插入到set里。
1.这个数等于x,显然最小波动值为0，我们也不需要再插入一个x放到set里了。
2.这个数大于x,通过set的特性可以很轻松的找到这个数的前驱，也就是小于x的第一个数。将两个数分别减去x,对绝对值取个min就好了。此时要将x插入到set中。
此方法来自 https://www.luogu.com.cn/blog/Okarin/solution-p2234

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
set<int>s;
set<int>::iterator k,a;
int n,x,ans=0;
int main() {
    s.insert(192608170);
    s.insert(-192608170);
    scanf("%d",&n);
    for(register int i=1; i<=n; ++i) {
        scanf("%d",&x);
        if(s.size()==2) {
            ans+=x;
            s.insert(x);
        } else {
            k=s.lower_bound(x);
            if(*k!=x) {
                a=k;
                a--;
                ans+=min(abs(*a-x),abs(*k-x));
                s.insert(x);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

方法3: 嵌套循环

此方法来自同一个机房小伙伴提供：超链接

#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;
}

方法4：双向链表

加入点可以用反向删除点来处理
删除点只要将指向他的ne[]和pre[]（即前驱和后驱更改）
此方法来自：https://www.luogu.com.cn/blog/user11413/solution-p2234

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;
int n,ne[200001],ne1[200001],ys[200001],an;
struct gjh
{
   int v,w;
}mp[200001];
bool cmp(gjh a,gjh b){return a.v<b.v;}
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++)scanf("%d",&mp[i].v),mp[i].w=i,ne[i]=(i==n)?0:i+1,ne1[i]=(i==1)?0:i-1;
   an+=mp[1].v;
   sort(mp+1,mp+n+1,cmp);
   for(int i=1;i<=n;i++)ys[mp[i].w]=i;
   for(int i=n;i>=1;i--)
   {
        int ans=INT_MAX;
        if(ne[ys[i]]!=0)ans=min(ans,abs(mp[ne[ys[i]]].v-mp[ys[i]].v));
        if(ne1[ys[i]]!=0)ans=min(ans,abs(mp[ne1[ys[i]]].v-mp[ys[i]].v));
        if(ans==INT_MAX)ans=0;
        an+=ans,ne1[ne[ys[i]]]=ne1[ys[i]],ne[ne1[ys[i]]]=ne[ys[i]];
   }
   printf("%d",an);
   return 0;
}