[CF1254B2] Send Boxes to Alice

[CF1254B2] Send Boxes to Alice - 贪心,数论

Description

n 盒排成一列的糖果盒，每次可以取出某一盒一颗糖果放到相邻的糖果盒里，问使得所有盒子的里的糖果数 gcd>1 的最少移动次数。

Solution

只需要检验 sum 的质因子的 k 即可，其中 sum 表示所有糖果数量的和

对于一个确定的 k，顺序扫一遍所有元素，考虑到第 i 个元素时，它与右边的所有元素要发生一定量的交换，要么是给右边 res 个，要么是从右边拿 k-res 个

贪心，两种情况取最小即可，因为无论哪种情况，对后面部分内部的交换是没有区别的

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n, a[N], sum;

int solve(int k)
{
    int partsum = 0;
    int ans = 0;
    for (signed i = 1; i <= n; i++)
    {
        partsum += a[i];
        partsum %= k;
        ans += min(partsum, k - partsum);
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];

    vector<int> fac;
    int t = sum;
    for (int i = 2; i * i <= sum; i++)
    {
        if (t % i == 0)
        {
            t /= i;
            fac.push_back(i);
        }
    }
    if (t > 1)
        fac.push_back(t);

    if (fac.size() == 0)
    {
        cout << -1;
        return 0;
    }

    int ans = 1e18;
    for (auto i : fac)
        ans = min(ans, solve(i));

    cout << ans << endl;
}