题目传送门

一、双链表解法

1、需要记录原始数据。
2、为了按金额排序，同时还需要记录相应的第几天，所以引入了结构体。
3、按结构体排序后的结果组成了一个双链表，本质上就是按金额从小到大排序的链，而链表中保存的数据是天数，注意，是天数，而不是金额。就是哪一天排在哪一天后面。
4、倒着查找是本思路的精华。先从最后一天开始，根据上面的双链表，找出它的前驱和后继都是哪天，因为它是最后的一天，所以可以理解为找出的前驱和后继都是它前面的数字，这样，就可以直接计算了。
5、找出最后一天的最小波动值后，最后一天就没有存在的必要了，把它从链表中清除掉，防止后续的天计算时再错误的找到它。

#include <bits/stdc++.h>

using namespace std;

const int N = 32768;
int ans;

//结构体：某一天
//money:营业额，day:第day天
struct node {
    int money;
    int day;
} s[N];

//结构体的比较函数，以钱小在前，钱大在后进行排序
bool cmp(node x, node y) {
    return (x.money < y.money);
}

//双链表的声明
int n, nex[N], pre[N], a[N];

int main() {
    //边界初始值
    memset(a, 0x3f, sizeof a);
    //输入
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];            //原始数组,第1，2，3 ...天的营业额是多少
        s[i] = {a[i], i};     //为了按营业额排序，但还需要保留是哪天的信息，没办法，只能使用结构体
    }
    //排序
    sort(s + 1, s + 1 + n, cmp);//按金额由小到大排序

    //"动态查找前驱后继"，可以用链表的离线做法
    //创建结构体+双链表,按金额排序后，日期的前后关系。
    for (int i = 1; i <= n; i++) {
        nex[s[i].day] = s[i + 1].day;
        pre[s[i].day] = s[i - 1].day;
    }

    //从后向前,这个非常棒！只有从后向前才有符合题意要求：这个数字之前的数字！
    for (int i = n; i >= 2; i--) {
        int a1 = a[nex[i]]; //后继节点的值
        int a2 = a[pre[i]]; //前驱节点的值
        ans += min(abs(a1 - a[i]), abs(a2 - a[i]));
        //删除当前结点,防止前面的节点错误的找到它
        nex[pre[i]] = nex[i];
        pre[nex[i]] = pre[i];
    }
    //第一天的最小波动值为第一天的营业额
    ans += a[1];
    //输出
    cout << ans << endl;
    return 0;
}

二、STL解法

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
set<int> s;//set 自带排序功能，强！set本身就是一种有序的容器。
//如果想要得到降序排序
//https://blog.csdn.net/weixin_38314865/article/details/113626709
int n, x, ans;

int main() {
    //set中放入极大和极小值,这个放入极大与极小值的技巧太棒了，可以有效避免越界等问题，值得背诵~
    s.insert(INF);
    s.insert(-INF);
    //读入
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        //如果set是空，只有极大与极小值时.也就是第一个
        if (s.size() == 2) {
            ans += x;
            s.insert(x);
        } else {
            //set居然支持二分法搜索~太棒了
            //lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素
            auto k = s.lower_bound(x);
            //如果不相等时（相等就是零了，不需要加入）
            if (*k != x) {
                auto a = k;
                a--;
                ans += min(abs(*a - x), abs(*k - x));
                s.insert(x);
            }
        }
    }
    //输出结果
    cout << ans << endl;
    return 0;
}