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