Send Boxes to Alice

E. Send Boxes to Alice

首先求出每一个位置的前缀和。

对答案进行复杂度为\(\sqrt{a[n]}\)的遍历，因为最后的答案不可能大于\(\sqrt{a[n]}\)
for(ll j=2;j*j<=a[n];++j)

	if(a[n]%j==0)

    {

        Try(j);

        while(a[n]%j==0)

            a[n]/=j;

    }
在Try(j)函数中，求的是当因子为\(j\)时的操作数量
void Try(ll k)

{

    ll temp=0;

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

        temp+=min(a[i]%k,k-a[i]%k);

//    tst(k,temp);

    best=min(best,temp);

}
\(temp+=min(a[i]\%k,k-a[i]\%k)\)的原因是在位置\(i\)上，如果不是\(k\)的倍数，那么，要么是将这个位置上的多出来的糖放到后面去，要么从后面拿糖过来。

取这两种方法的最小值，最后再求一个极值。

另外还要注意的一点是，无穷大要开得足够大，不然也会wa

代码：

// Created by CAD on 2019/11/23.

#include <bits/stdc++.h>

#define INF 0x7fffffffffffffff

#define ll long long

using namespace std;

const int maxn=1e6+5;

ll a[maxn];

ll best=INF,n;

void Try(ll k)

{

    ll temp=0;

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

        temp+=min(a[i]%k,k-a[i]%k);

//    tst(k,temp);

    best=min(best,temp);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin>>n;

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

        cin>>a[i],a[i]+=a[i-1];

    for(ll j=2;j*j<=a[n];++j)

        if(a[n]%j==0)

        {

            Try(j);

            while(a[n]%j==0)

                a[n]/=j;

        }

    if(a[n]!=1) Try(a[n]);

    cout<<(best==INF?-1:best)<<endl;

    return 0;

}

巴特西

Send Boxes to Alice

最新文章

热门文章