我来解释一下......

题意

就是对于每一个新的营业额，向前寻找与它差值最小的数做差，总和就是答案

set的性质

set的重要性质有两个，一个是自动去重，另一个是自动排序，我们这里利用的是第二个性质

因为自动排序后，寻找与这个数差值最小的数就好找了，要么是第一个比它小的数，要么是第一个比它大的数，但考虑到会有与它相等的数，所以使用lower_bound，不用upper_bound

设这个数是$x$，s.lower_bound(x) 的结果为$it$

每一个数的最佳答案就是min(abs(x-* it),abs(x-*(--it)))

剩下的就是细节的问题了

两个细节

1： 第一个数的前后没有任何数，最小的波动就是自己，注意特判

2： 可能不存在比它大或者小的数，但可能它减掉$0$反而是最优情况，而这是不合法的，所以加上两个判断lower_bound的结果是否为$s.begin()$或$s.end()$即可

#include<bits/stdc++.h>
using namespace std;
#define ll long long
set<ll>s;
int main()
{
    ll n,x;scanf("%lld%lld",&n,&x);
    s.insert(x);ll ans=x;
    for(ll i=1;i<n;i++)
    {
        scanf("%lld",&x);ll mn=1e18; 
    	auto it=s.lower_bound(x);
    	if(it!=s.end())mn=min(mn,abs(x-*it));
		if(it!=s.begin())mn=min(mn,abs(x-*(--it)));
		s.insert(x);ans+=mn;
    }
    printf("%lld\n",ans);
    return 0;
}

吐个小槽

加强数据跟加强了一样，开$int$都能AC......

注意要特判 $i=1$ 的情况。

#include<bits/stdc++.h>
using namespace std;
multiset<int>s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,x;cin>>n>>x;
	s.insert(x);int ans=x;
	for(int i=1;i<n;i++)
	{
		cin>>x;int mn=1e9;
		auto it=s.lower_bound(x);
		if(it!=s.end())mn=min(mn,abs(x-*it));
		if(it!=s.begin())mn=min(mn,abs(x-*(--it)));
		s.insert(x);ans+=mn;
	}
	cout<<ans<<'\n';return 0;
}

题解1：使用set的解法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=(1ll)<<60;
int main()
{
    set<LL>s;
    s.insert(inf);
    s.insert(-inf);
    int n;scanf("%d",&n);
    LL ans=0;
    for(int i=1;i<=n;++i)
    {
        LL x;scanf("%lld",&x);
        if(s.size()==2)
        {
            ans+=x;
            s.insert(x);
        }
        else
        {
            auto it=s.lower_bound(x);
            if(*it!=x)
            {
                LL nxt=*it;
                LL pre=*(--it);
                ans+=min(abs(pre-x),abs(nxt-x));
                s.insert(x);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

题解2：使用splay的解法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e12; 
LL a[110000];
struct trnode{LL d;int n,c,f,ch[2];}tr[110000];int len,root;
void upd(int x){ tr[x].c=tr[tr[x].ch[0]].c+tr[tr[x].ch[1]].c+tr[x].n;}
void add(LL d,int f)
{
	tr[++len]=trnode{d,1,1,f,0,0};
	tr[f].ch[tr[f].d<d]=len;
	if(f==0)root=len;
}
void rotate(int x)
{
	int y=tr[x].f,z=tr[y].f,w=(tr[y].ch[1]==x),v=tr[x].ch[1-w];
	tr[y].ch[w]             =v;tr[v].f=y;
	tr[x].ch[1-w]           =y;tr[y].f=x;
	tr[z].ch[tr[z].ch[1]==y]=x;tr[x].f=z;
	upd(y);upd(x);
}
void splay(int x,int rt)
{
	while(tr[x].f!=rt)
	{
		int y=tr[x].f,z=tr[y].f;
		if(z!=rt)((tr[z].ch[1]==y)==(tr[y].ch[1]==x))?rotate(y):rotate(x);
		rotate(x);
	}
	if(rt==0)root=x;
}
int findip(LL d)
{
	int x=root;
	while(tr[x].d!=d&&tr[x].ch[tr[x].d<d])x=tr[x].ch[tr[x].d<d];
	return x;
}
int findnext(LL d,int w)
{
	int x=findip(d);
	if(tr[x].d>d&&w==1) return x;
	if(tr[x].d<d&&w==0) return x;
	splay(x,0);x=tr[x].ch[w];
	while(tr[x].ch[1-w])x=tr[x].ch[1-w];
	return x;
}
void ins(LL d)

set：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=(1ll)<<60;
int main()
{
    set<LL>s;
    s.insert(inf);
    s.insert(-inf);
    int n;scanf("%d",&n);
    LL ans=0;
    for(int i=1;i<=n;++i)
    {
        LL x;scanf("%lld",&x);
        if(s.size()==2)
        {
            ans+=x;
            s.insert(x);
        }
        else
        {
            auto it=s.lower_bound(x);
            if(*it!=x)
            {
                LL nxt=*it;
                LL pre=*(--it);
                ans+=min(abs(pre-x),abs(nxt-x));
                s.insert(x);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e12; 
LL a[110000];
struct trnode{LL d;int n,c,f,ch[2];}tr[110000];int len,root;
void upd(int x){ tr[x].c=tr[tr[x].ch[0]].c+tr[tr[x].ch[1]].c+tr[x].n;}
void add(LL d,int f)
{
	tr[++len]=trnode{d,1,1,f,0,0};
	tr[f].ch[tr[f].d<d]=len;
	if(f==0)root=len;
}
void rotate(int x)
{
	int y=tr[x].f,z=tr[y].f,w=(tr[y].ch[1]==x),v=tr[x].ch[1-w];
	tr[y].ch[w]             =v;tr[v].f=y;
	tr[x].ch[1-w]           =y;tr[y].f=x;
	tr[z].ch[tr[z].ch[1]==y]=x;tr[x].f=z;
	upd(y);upd(x);
}
void splay(int x,int rt)
{
	while(tr[x].f!=rt)
	{
		int y=tr[x].f,z=tr[y].f;
		if(z!=rt)((tr[z].ch[1]==y)==(tr[y].ch[1]==x))?rotate(y):rotate(x);
		rotate(x);
	}
	if(rt==0)root=x;
}
int findip(LL d)
{
	int x=root;
	while(tr[x].d!=d&&tr[x].ch[tr[x].d<d])x=tr[x].ch[tr[x].d<d];
	return x;
}
int findnext(LL d,int w)
{
	int x=findip(d);
	if(tr[x].d>d&&w==1) return x;
	if(tr[x].d<d&&w==0) return x;
	splay(x,0);x=tr[x].ch[w];
	while(tr[x].ch[1-w])x=tr[x].ch[1-w];
	return x;
}
void ins(LL d)
{
	if(root==0) add(d,0);
	else
	{
		int x=findip(d);
		if(tr[x].d==d) tr[x].n++,splay(x,0);
		else            add(d,x),splay(len,0); 
	}
}
int main()
{
	int n;scanf("%d",&n);
	root=len=0;ins(-inf);ins(inf);
	LL s=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		if(i==1) s+=a[i];
		else if(i==2) s+=abs(a[1]-a[2]);
		else
		{
			int x=findip(a[i]);
			if(tr[x].d!=a[i])
			{
				int q=findnext(a[i],0),h=findnext(a[i],1);
				s+=min(abs(a[i]-tr[q].d),abs(a[i]-tr[h].d));
			}
		}
		ins(a[i]);
	}
	printf("%lld\n",s);
	return 0;
}