题解 CF1254B2 【Send Boxes to Alice (Hard Version)】
y2823774827y
2019-11-20 08:08:46
[My blog](https://www.cnblogs.com/y2823774827y/p/11895446.html)
## 题意
> n个数字的序列a，将i位置向j位置转移x个(a[i]-x,a[j]+x)的花费为$x\times |i-j|$，最终状态可行的条件为所有a[i]均被K整除(K>1)，求最小花费
## 做法
$sum=\sum\limits a$，则$K|sum$
- 有$K1|sum,K2|sum$，若$K1|K2$，则转移到被K1整除比转移到K2更优。这个是显然的，所以最终可能成为最优解的K个数为$logsum\le 40$
对于一个枚举到的K，将$b[i]=a[i]\% K$
对于b不为0的位置，我们类似贪心得考虑
- 仅有前面一个位置pre不合法：因为如果有两个，在之前我们可以合成一个
- 如果b[i]可以与前一个补满(b[i]可能还会有多余的)，考虑从i转移到pre优还是pre转移到i优
- 如果b[i]不能补满前一个，这个时候我们考虑如果能补满会补到哪里，然后更新一下pre
## Code
比赛时调了好久，码风有点奇怪
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long long ll;
const LL maxn=1e6+9;
const ll inf=0x3f3f3f3f3f3f3f3f;
LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}return x*f;
}
LL n,T,tot;
ll sum;
LL a[maxn],b[maxn];
ll bel[maxn];
bool Check(ll x){
for(LL i=1;i<=tot;++i) if(x%bel[i]==0) return false;
return true;
}
int main(){
n=Read();
for(LL i=1;i<=n;++i) a[i]=Read(),sum+=a[i];
/*srand(time(NULL));
n=1000000;
for(LL i=1;i<=n;++i) a[i]=rand()%1000001,sum+=a[i];
printf("%lld\n",sum);*/
for(LL i=2,up=sqrt(sum);i<=up;++i) if(sum%i==0){
if(Check(i)) bel[++tot]=i;
if(Check(sum/i)) bel[++tot]=sum/i;
}
if(Check(sum)) bel[++tot]=sum;
// printf("%d\n",tot);
if(sum==0 || sum==1){
puts("-1"); return 0;
}
if(!tot){
puts("0"); return 0;
}
ll ans(inf);
for(LL k=1;k<=tot;++k){
ll x(bel[k]),nw(0),ret(0);
LL l(1),pre(0);
for(LL i=1;i<=n;++i){
b[i]=a[i]%x;
if(!b[i]) continue;
if(nw){
if(x-nw>b[i]){
if((x-nw)*(i-pre)>nw*(i-pre)) ret+=nw*(i-pre),pre=i;
else ret+=b[i]*(i-pre);
nw+=b[i];
}else{
ret+=(std::min(x-nw,nw))*(i-pre);
nw=b[i]-(x-nw);
if(nw) pre=i;
}
continue;
}
nw=b[i];
pre=i;
}
ans=std::min(ans,ret);
// printf("(%lld,%lld)\n",x,ret);
}
printf("%lld\n",ans);
return 0;
}
```