题解：AT_arc211_a [ARC211A] Banned X 2

nbhs23a28 · 2025-12-01 16:10:51 · 题解

简单题，随便注意一下就结束了，10min 想完并写完。

本题要求给定 1 到 9 各若干个，要求最少添加多少个数字能使重排后任意两相邻数和不为 10。

考虑把相同数堆积起来，这是我们发现 5 是个奇特的不能堆积的数，且不与其他数和为 10。于是我们把有 5 情形拎出来考虑——若 5 的个数过多，多于所有其他数个数和，只需填满相邻 5 之间空隙即可，答案为 5 的个数减去其他数个数和再减 1；否则将其他数加上一个 5 从小到大排序，其他 5 随机插空（不与 5 相邻），没有任何冲突，答案为 0。

至于没有 5 情形，先把所有数从小到大排序，若中间有和为 10 冲突情况，若只有 2 种数，加一个 5 缓冲，答案为 1；否则一定可以通过一边相邻交换化解冲突，答案为 0。