题解：CF1949K Make Triangle

weitianyi · 2024-11-27 17:13:19 · 题解

这是一道很有意思的构造题，思路来源于官方题解。

首先，我们考虑能组成三角形的条件：对于任意一个集合 A，都应该满足 sum_A < \frac{sum}{2}。

那么，我们可以考虑一些不合法的条件, 我们设 S=\frac{sum}{2}, 假设 n_a \leq n_b \leq n_c 并且 x_i 递增：

我们以此为启发，想一想更为一般的情况。

考虑当前有三个集合分别剩下 l_a,l_b,l_c 个位置可以放，当前的和为 sum_a, sum_b, sum_c，那么我们可以考虑如果有界必须满足的条件有哪些，可以仿照上面, 设剩下的元素 x'_i 从小到大排列：

1. 对于任意集合 u，都有 sum_u + \sum\limits_{i = 1}^{l_u} x'_i < S。
2. 存在一个集合 u，并且该集合不为满，都有 sum_u + \sum\limits_{i = 1}^{l_u - 1} x'_i + x'_{n'} < S。

因此，我们只要证明这种判定方法是充分的即可。

我们可以假设 x'_{n'} 放的集合是 a, 剩下的元素随便放在 b 和 c 中，如果 b 和 c 都满足条件,那么就万事大吉了，如果不对，那就交换调整。

我们假设 b 中的和 \geq S，那么 a 和 c 中的元素一定可以随意交换，因为 a 和 c 中的元素和都 <S。

我们考虑 b 和 c 中的元素，我们考虑 c 会不会因此不满足条件。容易得到 x'_{n'} 在 a，所以 c 的和不会超过 S-x'_{n'}, 考虑到换入的最大是 x'_{n'}，换出的最小是 1，那么换完后 c 的和不会超过 S - 1。因此，只要 b 不符合要求，那么 b 和 c 中的元素可以任意互换。

那么我们继续考虑 a 和 b 中的元素，只要 b 不符合条件，那么交换 a、c 和 b、c 就一定能行。综上所述，因为满足第一条性质，那么一定可以通过交换使得原本不符合要求的 b 变得符合要求。

因此，我们可以使用一种极其简单的构造方法，将 x_i 从大到小依次加入，那么如果满足上面的两条判定，直接插入一个合法的集合即可，可以参考如下通过代码：MyCode。