自动搬运

查看原文

来自洛谷，原作者为

	vegetable_king 全身全霊！MORE MORE JUMP!!

搬运于2025-08-24 22:08:42，当前版本为作者最后更新于2021-07-30 20:33:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在博客食用更佳。

我看了一下题解区，大多数人用的都是 map 和 vector，还有一个用平衡树做的，没有人用 set，我就写了这篇题解。

思路

为什么要用 set？

我真的搞不懂为啥没有人用 set，题目里的这句话就让我第一时间想到了 set：

如果已经有相同长度的木材那么输出 Already Exist。

我们要用到的函数

我觉得这道题用 set 真是再合适不过了。

set 里面的 insert(x) 函数其实是有返回值的，会返回一个这样的奇怪的东西：pair<set<int>::iterator,bool>。

返回的这个 pair 到底是什么意思呢？

这个 pair 的第二项是一个 bool 类型的东西，代表插入是否成功。（意思就是只有集合里没有 x 的时候才能插入成功），第一项是一个迭代器，如果插入成功的话，它会返回 x 在集合里的位置，我们可以这样：

set<int> s;
set<int>::iterator p = s.insert(x).first;

以后用 *p 就可以得到 x 啦！

检测是否有相同长度的木材：

if (!s.insert(t).second) cout << "Already Exist\n";

一行直接解决问题！STL大法好

这是啥意思呢？如果有相同长度的木材，插入就会失败，pair 的第二项就会返回 false，如果没有，!s.insert(t).second 这个语句就直接实现了插入的目的，这就是我说 set 更方便的原因。

set.empty() 可以直接返回集合是否为空。

虽然 set 也有 lower_bound() 和 upper_bound()，但是，

set.lower_bound(x) 是返回第一个大于等于 x 的位置，

而 set.upper_bound(x) 是返回第一个大于 x 的位置，

set.find(x) 会返回第一个 x 的位置。如果没有 x，则会返回 set.end()。

set.erase(iterator)，删除定位器 iterator 指向的值

set.erase(first,second)，删除定位器 first 和 second 之间的值

set.erase(key_value)，删除键值 key_value 的值

结合刚刚讲的这些函数，我们可以写出代码的第二部分——出货。（s 已经被定义为 set<int>）

if (s.find(t) != s.end()) cout << t, s.erase(s.find(t)); // 找得到
else { // 找不到
	lwb = l2 = l3 = s.lower_bound(t);
	if (lwb == s.begin()) cout << *lwb, s.erase(lwb); // 特殊情况1，如果在最开始
	else if (lwb == s.end()) cout << *(-- l3), s.erase(l3); // 特殊情况2，如果在末尾
	else if (*lwb - t < t - *(-- l2)) cout << *(l3), s.erase(l3); // 选比较长的
	else cout << *(-- l3), s.erase(l3); // 选比较短的
}
cout << endl;

那么多方便的函数，果然还是 STL 大法好啊！还不快去用起来？

代码

#include <iostream>
#include <set> 

using namespace std;

int n, op, t;
set<int>::iterator lwb, l2, l3;
set<int> s;
int main(){
	cin >> n;
	for (int i = 1;i <= n;i ++){
		cin >> op >> t;
		if (op == 1){
			if (!s.insert(t).second) cout << "Already Exist\n";
		}
		else {
			if (s.empty()){
				cout << "Empty\n";
				continue;
			}
			if (s.find(t) != s.end()) cout << t, s.erase(s.find(t));
			else {
				lwb = l2 = l3 = s.lower_bound(t);
				if (lwb == s.begin()) cout << *lwb, s.erase(lwb);
				else if (lwb == s.end()) cout << *(-- l3), s.erase(l3);
				else if (*lwb - t < t - *(-- l2)) cout << *(l3), s.erase(l3);
				else cout << *(-- l3), s.erase(l3);
			}
			cout << endl;
		}
	}
}

32 行直接搞定，大概是最短的代码了。

本文部分内容选自C++中set用法详解，作者byn12345，如果想了解 set 的更多使用方法，这篇文章值得一看。