send boxes to alice(easy version)

题意

有$n(1\leq n\leq 10^5)$个盒子，每个盒子有$a_i(0\leq a_i \leq 1)$个糖果，你每一次可以将第$i$个盒子里的糖果放到第$i-1$或$i+1$个盒子中（如果盒子存在）。最后要使每个盒子的糖果数量都整除$k(k>1)$（注意盒子可以为空），问最小操作数。

分析

$(1)$因为糖果是类似于平铺的形式，堆叠时，我们可以发现所有存在糖果的盒子中数量均为$k$。若存在一个盒子中有$2*k$个糖果，在平铺到堆叠的过程中，将另外$k$个糖果分在更近的盒子能得到更小的答案。

$(2)$设糖果总数为$cnt$，所有存在糖果的盒子数量均为$k$，我们又可以发现，最小的操作是将$1$~$k$、$k+1$~$2k$、……、$ik+1$~$(i+1)*k$放在一起，即将相邻的$k$个放在一堆。

$(3)$对于某$k$个糖果，需要找到一个盒子，这个盒子到这$k$个糖果的距离最小(kNN算法)。我们将糖果看成数轴上的点，运用高一的绝对值知识（我忘了，我向高中数学老师谢罪）。

• 若$k$为奇数，则将该盒子设置为最中间糖果所在的盒子
• 若$k$为偶数，则将该盒子设置为最中间两个糖果中任意一个所在的盒子

即对于$ik+1$~$(i+1)*k$来说，第$k-i/2$个盒子，设其坐标为$ave$。

$(4)$为降低时间复杂度，我们采取前缀的思想，$sum[i]$表示坐标$i$之前的糖果的坐标总和（没糖果的盒子不加），$num[i]$表示坐标$i$之前有多少糖果。

$(5)$枚举可以被$cnt$整除的$k$，模拟$(2)$的过程，设$first$为第$ ik+1$个糖果的坐标，$last$为第$(i+1)k$个糖果的坐标，那么每个循环都得加上$(num[ave] - num[first - 1])*ave-(sum[ave] - sum[first - 1])+(sum[last] - sum[ave])-(num[last] - num[ave])ave$，意思为$ave$之前的操作次数加上$ave$之后的操作次数，最后取最小值

$(6)$记得开$long\ long$，$INF$也记得开大一点。

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define LL long long
#define pii pair<int,int>
#define int ll
using namespace std;
const int maxn = (ll) 1e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f3f3f3f3f;
int a[maxn];
int cnt = 0;
int sum[maxn];
int num[maxn];

signed main() {
    start;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        num[i] = num[i - 1] + x;//前缀数量
        if (x) {
            a[++cnt] = i;
            sum[i] = i;
        }
    }
    for (int i = 1; i <= n; ++i)//前缀坐标和
        sum[i] += sum[i - 1];
    int ans = inf;
    for (int i = 2; i <= cnt; ++i) {
        if (cnt % i == 0) {
            int tmp = 0;
            for (int k = i; k <= cnt; k += i) {//k为最后的糖果
                int first = a[k - i + 1];
                int last = a[k];
                int ave = a[k - i / 2];
                int num1 = num[ave] - num[first - 1];
                int num2 = num[last] - num[ave];
                int tot1 = sum[ave] - sum[first - 1];
                int tot2 = sum[last] - sum[ave];
                int t = num1 * ave - tot1 + tot2 - num2 * ave;
                tmp += t;
            }
            ans = min(ans, tmp);
        }
    }
    if (ans == inf)
        cout << -1;
    else
        cout << ans;
    return 0;
}

赏

谢谢你请我吃糖果