题目

题目背景

在一座高科技城市中，小A负责管理城市中的能量传输系统。城市中有一排能量节点，每个节点上储存了少量的能量，表示为 $0$ 或 $1$ 单位。

题目描述

由于城市计划升级，所有节点中的能量都需要调整，使得每个节点的能量都能整除一个特定的数 $k$（其中 $k>1$）。小A可以通过操作将能量从一个节点传输到相邻的节点，但每次只能移动 $1$ 单位的能量。

现在，王老师的目标是以最少的操作次数完成这个任务，确保所有节点的能量都满足被 $k$ 整除的要求。

你能帮助他计算出所需的最小操作次数吗？

输入格式

一个整数 $n$ 表示能量节点的数量。

接下来一行包含 $n$ 个整数 $a_1,a_2,...,a_n$ 表示每个节点中初始的能量数量。

输出格式

输出一个整数，表示完成目标所需的最小操作次数。

输入输出样例 #1

输入 #1

5
1 0 1 0 1

输出 #1

4

输入输出样例 #2

输入 #2

10
1 0 1 0 1 0 0 1 0 1

输出 #2

14

说明/提示

样例1解释 最优解为将 $a_1$的能量移到 $a_2$ 再移到 $a_3$。 将 $a_5$ 的能量移到 $a_4$ 再移到 $a_3$。 得到 $0,0,3,0,0$，均为 $3$ 的倍数。

数据范围

对于 $60\%$ 的数据，$1≤n≤10$

对于 $100\%$ 的数据，$1≤n≤10^5,0≤a_i≤1$

题解

取模的性质： $a \mod{p} + b \mod{p} = (a + b) \mod{p}$

$\because$ 每个节点 能量被 $k \gt 1$ 整除

即 最后总能量 能量被 $k \gt 1$ 整除

又 $\because$ 能量传输不改变总能量

$\therefore$ 总能量 能量被 $k \gt 1$ 整除

设 总能量（即 $1$ 的个数）为 $cnt$

首先，要使操作次数最小

先要将 $cnt$ 个 $1$ 分成 $m = cnt / k$ 组

再处理每组，

$\because$ 所有点到中位数的距离和一定最小

$\therefore$ 将每组的 $1$ 移动到该组的中位数位置

综上所述，最优策略是，将 $cnt$ 个 $1$ 分成 $m = cnt / k$ 组，将每组的 $1$ 移动到该组的中位数位置， 其中 $k \gt 1$ 且 $k$ 为 $cnt$ 的约数。

怎么计算每组数字到中位数的距离呢？

用前缀和计算即可

代码

辅助数组

if (a[i]) {
    pos[++cnt] = i;
    sum[cnt] = sum[cnt - 1] + pos[cnt];
}

其他代码

for (k = 2; k <= cnt; k++) {
    if (cnt % k != 0) continue;
    int m = cnt / k;
    LL res = 0;
    for (int i = 1; i <= m; i++) {
        int l = (i - 1) * k + 1;
        int r = i * k;
        int mid = l + k / 2;
        // [l, mid]
        int dis_l = mid - l;
        LL ans_l = sum[mid] - sum[l - 1];
        res += pos[mid] * dis_l - ans_l;
        // [mid + 1, r]
        int dis_r = r - (mid + 1);
        LL ans_r = sum[r] - sum[mid + 1 - 1];
        res += ans_r - pos[mid] * dis_r;
    }
    ans = min(ans, res);
}