题解 P3586 【[POI2015]LOG】

HTensor · 2020-12-18 15:10:00 · 题解

提供一个简明的关键性质证法。

性质：对于每次询问，设大于 s 的数有 x 个，小于 s 的数和为 sum ，若 sum \geq (c-x) \times s 则有解，否则无解。

证明：

原问题等价于构造 s 个长度为 c 的数列，数列中数字的意义为被减 1 的元素下标，规定每个数列中不能有重复数字，值为 a_i 的元素下标最多在 a_i 个数列中出现。

显然地，若 a_i \geq s 我们可以让第 i 个元素在所有数列中全部出现。

对于剩下的空位置，对于所有的 a_i < s 可以填入 \sum a_i 次。即 sum 次。

证毕。