将所有数都减去 ,于是初始值变为 。若 ,对所有数作变换 即可,因此下文假设 。
令 、、、、。最终所有数必定等于整体平均值 。无论进行多少次操作,每个数写成最简分数后其分母始终是 的幂,因此若 不是 的幂则不可能完成。
设 是 的幂。由于 ,有 。令 ,则最少操作次数为 。
Construction
当 时, 为奇数。先构造 个大小为 的组,每组中 的数量分别为 。再将剩余元素分成 个大小为 的组。
Bound
若两个下标曾在同一次操作中被选中,就在它们之间连边得到图 ,设其连通分量数为 。若某个连通分量的大小为 ,则该分量最终的总和 必须为整数,因此 是 的倍数。将各连通分量的大小写成 ,则 。
总时间复杂度为 。
Solution written by GPT5.6
若某个大小为 的组中有 个 ,则该组中 的数量必须分别为 、、。因此 ,并且所有大小为 的组中 的总和应为 。由 的定义可知这样的分配总是存在。
每个组都可以恰好用“组大小减 ”次操作变为相等。大小为 的组由 构成且总和为奇数。对于大小为 的组,将所有值除以 后会得到总和为奇数的 组。
考虑一个大小为 、元素属于 、总和为奇数 的组。逆向构造操作。开始时,想象有 个最终平均值 。从两个相等的当前值 中,固定其中一个位置为原始整数 ,并将另一个位置逆向变为 ,即可逆向恢复一次平均操作。
当活跃元素个数为 时,令 。所有活跃元素的小数部分均为 ,因此只会出现 和 两种值。设较大值的个数为 ,并把相同类型的值两两配对。
下一层的活跃元素个数为 。对于每个状态 ,之后能够恢复的未恢复 的数量构成一个整数区间。当 时,只有 和 两种状态。利用上述转移可以从较小的 开始计算这些区间。使用前缀和后缀最小值、最大值,可以在 时间内处理一层,而所有层大小之和也是 。实际恢复时,只需选择一个使下一状态仍落在可行区间内的转移。最后将记录的逆向操作倒序,即可得到恰好 次正向操作。
设第 个连通分量中初始有 个 。该分量的总和为 ,所以 。由于 为奇数,
因此 。形成一个大小为 的连通分量至少需要 次操作,所以总操作次数至少为
。