【Codeforces】【黄题地雷/诈称】CF1906M Triangle Construction

· · 题解

记 S=\sum\limits_{k=1}^N A_k。容易得到答案的一个上界 \lfloor \frac{S}{3} \rfloor。

尝试贪心构造一种方案。记 M=\max\limits_{k=1}^N A_k。记 A_p=M。

若 M=1，那么每次选择相邻的三条边上的点即可达到上界。

若 M \ge 2，则取一个三角形，其两个端点在第 p 条边上，另一个端点在相邻的特殊点数较多的边上。在这样操作后我们得到了一个新的 A。对这个新的 A 删去所有 0 后反复操作直到不能取新的三角形。

发现这样的过程终止时下面的条件至少满足其一：

  1. 最终的 M \le 1；
  2. 最终的 A 只有一个元素。

若满足条件 1，将剩下的点按 M=1 的做法组合即可达到 \lfloor \frac{S}{3} \rfloor 的上界。

对于条件 2，一种可能性是 M>\frac{2}{3}S，此时每次取三角形时该过程均在一条固定的边上取两个点，在剩余的部分取一个点，这样最终能获得一种 S-M 个三角形的方案。因为每一个三角形必定占用 S-M 个点中的至少一个，所以此时我们已经得到了最优方案。

考虑 M \le \frac{2}{3}S 的情况。若 3 \le S \le 5，则恰好可以取一个三角形后达到上界。下设 S \ge 6。设取一个三角形后每条边上未占用的特殊点数量的最大值为 M'。那么有下面的情况：

因此在满足性质 M \le \frac{2}{3}S 时，可以使用数学归纳法证明上面的构造方法总能取到上界。

综上所述，原题的答案为 \min \{\lfloor \frac{S}{3} \rfloor, S-M\}。

时间复杂度 \Theta(n)。代码太简单就不放了。