题解：P17716 [HexOI Round 1] 变魔术 / magic

Doris0929 · 2026-10-20 16:18:56 · 题解

思路

题目允许随意给淘汰的积木分堆，因为是淘汰小的，那显然把要扔掉的积木全部拆成单块（大小为 1） 对我们最有利。此时我们保留的这一堆，只要权值和大于等于被淘汰积木里的最大值就行。

所以想让某个积木活到最后，比它小的积木都无所谓，真正的阻碍只有那些比它大的积木。我们需要把比它大的积木踢出局。

把积木按美丽度升序排序：a_1 \le a_2 \le \dots \le a_n，前缀和记为 \mathit{pref}[i] = \sum_{j=1}^i a_j。

考虑怎么踢掉排在后面的大积木 a_k：

要想战胜 a_k，最赚的做法肯定是把排在它前面的所有积木全部拉过来抱团，此时能凑出的最大战力就是 \mathit{pref}[k-1]。

• 如果 \mathit{pref}[k-1] < a_k：这意味着哪怕全场所有比 a_k 小的积木加在一起，都没有 a_k 大。此时 a_k 就不可能被比它小的顶掉，所有比 k 小的积木都不可能留到最后。
• 如果 \mathit{pref}[k-1] \ge a_k：前面的积木合作可以顶掉 a_k。

因此，只要一个积木后面存在任何一个不可能被顶掉的大积木，它就必死无疑。

我们只需要线性扫一遍，找到最后一个顶不掉的积木的位置（即最大的满足 \mathit{pref}[k-1] < a_k 的 k）：

• 排序后位置在 k 之前的积木：无论如何都过不去第 k 关，答案为 0。
• 排序后位置在 k 及之后的积木：比它们大的数都能被前面的前缀和顺次消掉，随后它们自己就是场上最大值，可以直接清场，答案为 1。

若全程都不存在这样的断点，说明所有人都能通关。

复杂度分析

• 时间复杂度：排序 O(n \log n)，求前缀和与找断点 O(n)，总时间复杂度 O(n \log n)。
• 空间复杂度：存储数据与前缀和数组，O(n)。

代码

::::warning[注意]{open}