洛谷 P2234 [HNOI2002] 营业额统计（详解）c++

题目链接：P2234 [HNOI2002] 营业额统计 - 洛谷

1.题目分析

输入输出样例：根据题目知第一天的最小波动值为第一天的营业额，所以第一天的最小波动值是5，算出第二天的最小波动值就说拿前面的数分别减当前的数，并且取一个最小值，前面就一个数5，所以就用5-1再加上个4就可以了，依次算出结果：5+4+1+0+1+1=12

2.算法原理

针对某一天的营业额x，找出前面的数中哪个数离它最近，也就是根小于等于x的最小值y或者小于等于x的最大值z，找到这两个值后分别让y-x和z-x取min就可以了

如何获取y和z
y我们可以利用set里面的lower_bount，把x前面的数全部放到set里面，在针对x调用lowerbount就可以了；z需要用到迭代器的运算，比如下图是一个有序序列，it指针指向第四个元素，—it会让指针向前移动，++it会让指针向后移动，如果迭代器it是大于等于x的最小值，我们只需要让it—，就可以找到它前一个位置，就是小于等于x的最大值

越界问题
假设只有一个营业额，调用lower_bound，it会指向这一个元素，，再—it会指向他前面的一个位置，但前面的位置是一个空，就会出现越界访问的情况，我们可以创建迭代去之前插入两个左右护法左边的护法是负无穷大，右边的护法是正无穷大，就不会出现越界访问的情况，并且要考虑护法的值不能干扰最终的结果，因为有可能—it之后把三角形里面的值带入到上面的公式取min的话，会干扰结果，因此我们要让三角形里面的值永远取不到min才行，这道题的数据范围是10的六次方，只要我们让负无穷的值等于-10的7次方，不管x等于多少，-10的7次方-x与it指向的值-x做对比，前者永远不可能取到最小值，此时正负无穷大放在这里就不会干扰结果，也就是说这道题是取小操作，只要两边搞成无穷大，两边减完x的绝对值一定不可能取到最小

代码：

#include <iostream>
#include <set>
using namespace std;

//INF 无穷大
const int INF = 1e7 + 10;

int n;
set<int> mp;

int main()
{
	cin >> n;
	int ret; cin >> ret;
	mp.insert(ret);

	//左右护法 - 防止越界访问
	mp.insert(-INF); mp.insert(INF);

	for (int i = 2; i <= n; ++i)
	{
		int x; cin >> x;
		//找距离x最近的那一个
		//lower_bound返回的是x或者比x大一点的指针
		//赋值给新指针tmp--指向it左边，比x小一点的数，越界问题上面已解决
		auto it = mp.lower_bound(x);
		auto tmp = it;
		tmp--;

		//找到的数和它本身一样，最小波动值为0，不需要判断
		if (*it == x) continue;	
		
		//取最小波动值
		ret += min(abs(*tmp - x), abs(*it - x));
		mp.insert(x);
	}
	cout << ret << endl;

	return 0;
}