CF1255E2: Send Boxes to Alice (Hard Version)

移动糖果等价于给前缀和加一或减一;枚举总和的质因子 k,把每个前缀和调整到最近的 k 的倍数。

来源 Codeforces 1255 E2 · 难度 Codeforces 2100 · 时间 1 s,空间 256 MB · 标签 贪心 / 数学 / 数论 / 前缀和

题目描述

有 𝑛 个盒子,第 𝑖 个盒子初始有 𝑎𝑖 颗糖果。一次操作可以把一颗糖果从盒子 𝑖 移到相邻的盒子 𝑖−1 或 𝑖+1。

求最少操作次数,使得存在整数 𝑘>1,每个盒子中的糖果数都能被 𝑘 整除;无解输出 −1。

1≤𝑛≤106,0≤𝑎𝑖≤106,且至少有一个 𝑎𝑖>0。

题解

记前缀和

𝑠𝑖=∑𝑗=1𝑖𝑎𝑗.

把一颗糖果从盒子 𝑖 移到 𝑖+1,只有 𝑠𝑖 减少 1;反向移动则只有 𝑠𝑖 增加 1。因此一次操作等价于给某个前缀和加一或减一。

固定 𝑘>1。所有 𝑎𝑖 都能被 𝑘 整除,当且仅当所有 𝑠𝑖 都能被 𝑘 整除。于是每个 𝑠𝑖 都要调整到离它最近的 𝑘 的倍数。记

𝑟𝑖=𝑠𝑖−𝑘⌊𝑠𝑖𝑘⌋,

则调整 𝑠𝑖 的最小代价为

min(𝑟𝑖,𝑘−𝑟𝑖),

总代价为

𝐶(𝑘)=∑𝑖=1𝑛min(𝑟𝑖,𝑘−𝑟𝑖).

由于 𝑠𝑖 单调不减,按同一平局方向取最近的倍数后,调整后的 𝑠𝑖 仍单调不减,所以得到的盒子糖果数非负,方案合法。

总糖果数

𝑆=𝑠𝑛

必须被 𝑘 整除。若 𝑆=1,不存在 𝑘>1,输出 −1。

若 𝑘 是合数,取它的一个质因子 𝑝。𝑘 的倍数一定是 𝑝 的倍数,因此对每个 𝑠𝑖,到 𝑝 的倍数的距离不超过到 𝑘 的倍数的距离,即

𝐶(𝑝)≤𝐶(𝑘).

所以只需枚举 𝑆 的不同质因子。对每个质因子 𝑘,按上式在 𝑂(𝑛) 时间内计算 𝐶(𝑘),取最小值。

复杂度

分解 𝑆 为 𝑂(𝑆);若不同质因子个数为 𝜔(𝑆),总时间为

𝑂(𝑆+𝑛𝜔(𝑆)),

空间为 𝑂(𝑛)。答案可能超过 32 位整数范围,需使用 64 位整数。

参考

源码位置