set 和 map 的左右护卫 【刷题反思】

1. 相近的营业额

1.1 题目

题目描述：我们定义，一天营业额的最小波动 = min { | 该天以前某一天的营业额 - 该天营业额 | }

                  特别的，第一天的营业额最小波动为第一天的营业额

输入描述：第一行 n （n <= 32767），表示公司从成立到现在的天数

                  接下来 n 行每行有一个整数 ai （|ai| <= 10e6），表示第 i 天的营业额，可能存在负数

输出描述：一个正整数，表示每一天最小波动的和，保证结果小于 2^31

输入：

6

5

1

2

5

4

6

输出：

12

1.2 思想

对于每一个新的数 x ，我们总共要找到距离 x 最近的一大一小的两个数，可以将之前的数据放入到 set 中，对于大于等于 x 的值可以用 lower_bound 得到 set 中该值的迭代器，让迭代器进行（--）操作，可以得到比 x 小的最接近 x 的值，然后让各自与 x 的差值进行比较就可以得到最小波动值

值得注意的是：当对迭代器进行（--）操作时，如果 set 里的元素不够，可能非法访问，所以我们需要左右护法进行保护，而左右护法也不能干涉比较的结果，那左右护法可以趋于无穷（即这个情况下不可能取到的值）

1.3 模拟实现

#include<iostream>
using namespace std;
#include<set>
#include<cmath>
set<int> mp;
//注意近似无穷的值
int INF = 1e7+10;
int total;
int main()
{int n; cin >> n;int x; cin >> x;//先将第一天的值插入mp.insert(x);total += x;//添加左右护法mp.insert(INF);mp.insert(-INF);for(int i=2;i<=n;i++){int x; cin >> x;//取出大于等于 x 的值的迭代器auto it1 = mp.lower_bound(x);//找到最近的小于 x 的迭代器auto it2 = it1;it2--;//进行比较total += min(abs( *it1 - x ), abs( *it2 - x ));//最后将今天的 x 插入mp.insert(x);}cout << total << endl;return 0;
}

2. 相近的木材

2.1 题目

题目描述：有一个木材仓库，里面没有两个木材的长度相同，现在有不超过100000条操作：

                  进货格式：1 length：向仓库中放入长度为 length （不超过 10e9）的木材，如果已经存在，就输出 Already Exist

                  出货格式：2 length：仓库中取出长度为 length 的木材。如果没有刚好长度的木材，取 出仓库中存在的和要求长度最接近的木材。如果有多个符合要求，取出比较短。输出取出的木材长度。如果仓库为空，输出 Empty

输入：

7
1 1
1 5
1 3
2 3
2 3
2 3
2 3

输出：

3
1
5
Empty
2.2 思想

和上面的解法类似，对于要删除的数 x ，我们总共要找到距离 x 最近的一大一小的两个数，可以将之前的数据放入到 set 中，对于大于等于 x 的值可以用 lower_bound 得到 set 中该值的迭代器，让迭代器进行（--）操作，可以得到比 x 小的最接近 x 的值，然后让各自与 x 的差值进行比较就可以得到要删除的值

值得注意的是：当对迭代器进行（--）操作时，如果 set 里的元素不够，可能非法访问，所以我们需要左右护法进行保护，而左右护法也不能干涉比较的结果，那左右护法可以趋于无穷（即这个情况下不可能取到的值）

2.3 模拟实现

#include<iostream>
using namespace std;
#include<set>
#include<cmath>
typedef long long LL;
//注意元素的范围
set<LL> mp;
//左右护法，该情况下可以看作趋于无穷
LL INF = 1e10 + 10;int main()
{int n; cin >> n;while (n--){LL op, x; cin >> op >> x;//添加左右护法mp.insert(INF); mp.insert(-INF);if (op == 1){//如果 set 没有就插入if (mp.count(x)) cout << "Already Exist" << endl;else mp.insert(x);}else{//只有左右护法可以将 set 看作空if (mp.size() == 2) cout << "Empty" << endl;else{//取出大于等于 x 的值的迭代器auto it1 = mp.lower_bound(x);//找到最近的小于 x 的迭代器auto it2 = it1;it2--;//进行比较if (abs(*it1 - x) >= abs(*it2 - x)){cout << *it2 << endl;mp.erase(*it2);}else{cout << *it1 << endl;mp.erase(*it1);}}}}return 0;
}