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