Codeforces Round #601 (Div. 2) E2. Send Boxes to Alice (Hard Version)

题意

N个盒子，每个盒子有a[i]块巧克力，每次操作可以将盒子中的一块巧克力左移或右移，要求移动后的每个盒子中的巧克力数量都能被k整除（无视空盒子），求最小的操作数。(1<=N<=1e6,0<=a[i]<=1e6)

思路

• k只需考虑巧克力总数的质因子
• 考虑每个盒子的贡献，盒子中可以保存k的整数倍（k*i）块巧克力，从左向右递推，每个盒子保留最大数目的巧克力，假设剩余的巧克力数目为x,则有两种情况，一是，x全部给后一个位置的盒子，二是，由后一个位置的盒子给他(k-x)块巧克力。而无论是哪种情况，都不会影响后一个盒子剩余巧克力的数量。
• 分治的考虑这道题，将n个盒子视为两部分，每个部分能解决完k的整数倍（k*i）块巧克力，而两部分交换巧克力（距离为1）的最小代价就是对两部分的剩余巧克力取最小值，而任意两部分剩余的巧克力之和总为0或k
• 读入不能用cin

代码

#include <cstdio>

#include <iostream>

#include <vector>

#include <set>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 10;

int a[maxn],n;

ll sum[maxn];

inline ll solve(ll k){

	ll res=0;

	for(int i=1;i<=n;i++){

		ll x=sum[i]%k;

		res+=min(x,k-x);

	}

	return res;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",a+i);

		sum[i]=a[i]+sum[i-1];

	}

	ll tot=sum[n],ans=LLONG_MAX;

	for(ll i=2;i*i<=tot;i++){

		if(tot%i) continue;

		ans=min(ans,solve(i));

		while (tot%i==0) {

			tot/=i;

		}

	}

	if(tot!=1) ans=min(ans,solve(tot));

	if(ans!=LLONG_MAX)cout<<ans<<endl;

	else cout<<-1<<endl;

}