题解：AT_arc211_a [ARC211A] Banned X 2

玄学OIER荷蒻 · 2025-12-01 15:25:33 · 题解

题目大意

给定 9 个数 a_1,a_2,\cdots,a_9，a_i 表示初始序列 S 中数字 i 的个数。

你可以任意排序序列 S，然后问你需要最少再加几个数才能让 S 不存在相邻两数之和 =10 的情况。

解题思路

考虑怎么排最好。注意到 5 是特殊的，他不能和自己相邻，可以和其他任何数相邻。

我们把 5 尽量和其他数穿插的排，如果超过了其他数数量 +1，那就排不了了，这时候答案也很简单 就是 2 a_5 - \sum_{i=1}^9 a_i -1。否则就是 5 越多越好，可以良好的解决其他数字之间的冲突。

不管 5 的话只考虑其他 8 个数的话，冲突也很好解决。只要让所有数正序排序，就最多只会有一处冲突。 然后让最小的或者最大的数跑到中间来，就不会有任何冲突了。

这种方法只会在只有两种数字且这两种数字冲突的情况下没法用。显然这时候怎么排都会冲突，那就直接两种数全放一起中间插个 5 就行了，答案为 1。

综上， 2 a_5 - \sum_{i=1}^9 a_i -1 > 0 时，答案为 2 a_5 - \sum_{i=1}^9 a_i -1；否则如果只有两种数且这两种数冲突，答案为 1；其他的情况，答案为 0。

然后就做完了，感觉难度差不多下位黄吧。