自动搬运

查看原文

来自洛谷，原作者为

	SDLTF_凌亭风 人生的相遇相逢不存在 O(1)，愿每位 OIer 仍在路上

搬运于2025-08-24 22:47:49，当前版本为作者最后更新于2023-09-30 18:15:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

某网校讲了这个题，并且发现还可以交题解，那我来了。

我们这样去理解这个题目：有两个人 SD 和 LTF，还有 $n$ 个物品。SD 要选 $n-m$ 个，LTF 会在 SD 取了 $a_i$ 个之后抢走一个，并且第 $i$ 次他会按照一个优先级排列 $p_i$ 抢走还在场上的优先级最高的那个物品，并且每次的优先级不一定相同。

现在你就是 SD，我是 LTF。你要找到一个方案让字典序最小。

先从简单的方面来看，让字典序更小是很好考虑的。假设最后你选择的物品塞进了一个集合 $S$，一开始他是空的，所以你的任务就是：已知一个集合 $S$ ，问是否有方案得到 $S$。

注意到 $2^{-i}\geq \sum_{k = i + 1}^{n}2^{-k}(i\geq 1)$，优先满足前面的显然更优，于是你就让编号从小往大开始枚举。

那我就要开始打乱你的计划了。

假设这是我第一次取，我找到一个 $t$，使得 $p_1, p_2, \cdots, p_{t - 1}$ 所对应的物品全部被你拿走了，但是 $p_t$ 对应的物品正好没有，那按照优先级从高到低的规则，我肯定要拿走这个物品，换句话说，$p_1, p_2, \cdots, p_{t - 1}$ 必须在前 $a_1$ 次取走。

但是你这时候就能尝试第二次取了吗？不行！因为你不知道我第一次取了什么。

但你又发现，$p_t$ 在第 $a_1+1$ 次之后肯定是选不了的，要么是你选了要么是我选了。选不了的你不如就直接放掉让我抢走。

这样子再来考虑我的第二次抢夺，那就变成了和第一次一样的问题。

这样你依次考虑我每次抢夺，得到最初的集合 $S$ 中所有元素最晚在什么时候取走。按照最晚取走的时间排序填入方案并判断是否合法即可。

$O(n^3)$ 的复杂度，恭喜你完成实验！