题目描述

对于第i个营业额a[i],找出abs(a[i]-a[j]){j=1~i-1}的最小值,用ans累加起来并输出.

样例

输入样例
6
5
1
2
5
4
6

输出样例
12

算法

(set) $O(nlogn)$

浏览一下众大佬的题解，其实本蒟蒻的思路与”玩玩就好”神犇的题解思落相差无几，但是觉得大佬的操作有一点冗长（恕我直言）
所以打算在其基础上进行优化与补充
看到题目，便想到了set，set不光存储方便，而且支持lower_bound，感觉比较好用。
读入当前营业额时，利用set当中自带的lower_bound进行扫描，复杂度为O(logn)。
然后分两种情况:
1.如果i==1,则ans直接加上x
2.否则ans加上min(x-x的前驱,x-x的后继)–>这里的前驱与后继都是针对于数值大小来说得
注意事项
1.set中lower_bound返回的是指针
2.为了防止lower_bound返回指针是set.end()–>即寻找不到,应当预处理一下,在set当中预先加入无穷大与负无穷大这样可以方便判断

时间复杂度

O(nlogn)

参考文献

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