洛谷题单指南-线性表-P2234 [HNOI2002] 营业额统计

原题链接：https://www.luogu.com.cn/problem/P2234

题意解读：要计算每一天最小波动值的和，需要对每一天求最小波动值，再求和，如果暴力法，时间复杂度在1+2+3+……+32767≈5*10^8，可能会超时。

解题思路：

1、暴力法：由于本题测试数据比较水，实测暴力求解直接可以AC，由于没有技术含量，不做具体介绍。

2、set法：

对于每一个数x，只需要找前面出现的跟x最接近的数

那么，很容易想到，对出现的每一个数，维护一个有序的数据结构，当把x插入之前，找到x的前后数（刚好>=x的、刚好<x的），看差的绝对值哪个小即可

要维护有序的数据结构，set比较合适，另外set还提供了lower_bound(x)函数，可以在logN的复杂度查找第一个>=指定值的位置

100分代码:

#include <bits/stdc++.h>
using namespace std;

set<int> st;
int ans;

int main()
{
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++) 
    {
        cin >> x;
        int minx = INT_MAX;
        if(i == 1) minx = x;
        else
        {
            set<int>::iterator itr = st.lower_bound(x); //先查找>=x的第一个数的位置
            if(itr != st.end()) minx = min(minx, abs(*itr - x)); //计算第一个可能的最小波动值
            if(itr != st.begin())
            {
                set<int>::iterator itl = itr;
                itl--; //itl是<x的最大的数的位置
                minx = min(minx, abs(*itl - x)); //计算第二个可能的最小波动值
            }
        }
        st.insert(x); //将x插入set
        ans += minx;
    }
    cout << ans;

    return 0;
}