1 条题解
-
0
题目分析
为什么一定有解?
考虑把所有数全部转移到比如说 ,最终 ,取 即可。
思路 1
先分解质因数, 的取值只可能是 的质因数。
然后对每个质因数进行操作,即,使每个数变成 或者质因数的 倍。
先对每堆石头进行处理,处理为该堆石头的数量与它前一个质因数倍数的差值。(当这个数小于质因数,则算它与 的差值。)
比如 ,,当处理到质因数为 的时候,预处理为 (这里的 意味着已经是质因数的 倍,就可以不存了), 然后贪心一下,对预处理好的数组从大到小排序
这样我们对预处理好的数组做一下前缀和处理,当某一个时刻,
前缀和 = 后缀个数 * 质因数 - 后缀和的时候,前缀和即为当前答案。这里怎么理解呢?其实是:前面的数是用来往外拿,去补后面的数。那么
后缀个数 * 质因数 - 后缀和也就是把后缀的石堆补到质因数的 倍。(之前预处理的是它与质因数 倍的距离)思路 2
记 。
每次操作不改变所有数的总和 ,仅重新分配数值。因此,最终所有数均为 的倍数时, 必须是 的因子(即 )。
若 是合数(如 ),则其质因子(如 )必然也是 的因子。
将问题转化为 的倍数所需的操作次数不会多于 的倍数。因此只需枚举 的所有质因子作为候选 。
若 本身是质数,则唯一可行的 。此时最小操作次数为 (将所有数集中到最大值上)。
对 的每个质因子 ,计算将所有 变为 的倍数的最小操作次数:
-
余数处理
- 计算每项的余数 ,并保留非零余数( 无需调整)。
- 所有非零余数的和 必须是 的倍数(否则该 无解)。
-
贪心策略:双指针调整余数
- 排序余数:将非零余数数组 从小到大排序。
- 双指针调整:
- 左指针 指向最小余数,右指针 指向最大余数。
- 每次操作中,从 移出 到 :
- 减少该值, 增加该值(若 达到 则归零)。
- 累计操作次数为移出的数值。
- 更新指针:若 则 右移;若 则 左移。
- 正确性:小余数补充大余数至 的倍数,可最小化操作次数 。
-
操作次数的计算
- 最终操作次数为所有移出值的总和,即 。
复杂度:( 为质因子数)。
例如:设 , ,质因子 或 :
- :余数 → 非零余数 。
- 排序后 ,左指针 , 右指针 。
- 移 到 :, (归零)。
- 操作次数 。
- :余数 → 非零余数 。
- 移 到 :, (归零)。
- 操作次数 。
- 最终答案:。
-
- 1
信息
- ID
- 188
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者