[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)

题目链接

题意:

给定一个长度为 $n$ 的序列 $a$ ,$n \le 10^6$ ,每个数字 $a_i$ ,满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作,把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除($0$可以被任何数整除),操作过程要满足所有的 $0\le a_i$ 。

题解:

考虑操作完成之后的结果,如果每一个数字都能被 $k$ 整除,那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况,要么被 $k=其质因子$ 的情况包括,要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况,也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知,其质因子最多应该只有$10-20$种,而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法,也就是约 $10^6$ 。

那么我们就可以分解出来所有可能的 $k$ ,枚举他们来进行下一步的计算。现在问题就转化成了,给定一个数字 $k$ ,问最少需要多少次操作使得这个序列里所有的数字可以被 $k$ 整除。

按照每一个位置上的数字来看似乎很难计算出最优解,但是我们可以把所有的转移一视同仁作为一次操作,然后计算每一个间隔的贡献。

下文 $S_{i}$ 表示 $\sum_{j=1}^{i} a_{j}$

从第一个数字开始考虑,$1$到$2$之间的间隔(不妨把间隔视为传输每一个单位的管道)需要传递 $S_{1}\%k$ 或者 $k-S_{1}\%k$ 个单位才能让 $a_{1}\%k=0$ 。

由于我们要求的结果是最小值,所以这里可以尝试一下:先假定取了$min$,也就是我们先假设这根管道的贡献是 $min(S_{1}\%k,k-S_{1}\%k)$ 。

然后再考虑2到3之间的管道,类似于1到2的情况,要使得前2个数字都被$k$整除,则一定传递了 $S_{2}\%k$ 或者 $k-S_{2}\%k$ 个单位。$

注意:我们处理的顺序保证了,每次只需要考虑当前这个间隔的情况,比如我考虑2到3的间隔的时候就不需要考虑1到2的,我只需要保证我在这个间隔处往前面传递了$S_{2}\%k$ 或者 $k-S_{2}\%k$ 个单位就行了。至于传给$a_{2}$后它怎么处理,不需要担心,它无论收到多少个,只需要保证在1到2的管道中传给了$a_{1}$ $S_{1}\%k$ 或者 $k-S_{1}\%k$ 个单位就可以了。

这样从前往后考虑过每个管道之后,假如到最后一个数字 $a_{n}$ 我们还可以往前传递所需要的数字,也就是说有合法的解,我们就可以计算出所需要的答案了。

因此现在问题变成了,我们在每一步的时候这样贪心的选择,是否能得到合法的解?答案是肯定的。主要原因是我们确定了$k$ 是 $S_{n}$ 的因数,然后在每一步的过程中都凑齐令 $S_{i}$ 为k的倍数,这样就永远可以满足条件。比如拿最后一个数字来说,假如 $a_{n}$不能对 $S_{n-1}$ 凑齐 $k$的倍数,那么 $k \nmid (S_{n-1}+a_{n})$,这与 $k$ 是 $S_{n}$ 的因数是矛盾的,所以一定可以满足条件。以此往前类推,我们就可以证明按照我们的贪心策略,所有的 $S_{i}$ 都是可以合法构造的。至此这道题目就做完了。

wa点:

  • $INF$设置小了,原来以为 $10^{12}$ 就足够了,其实还要考虑到转移路径比较长的情况。
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e6+5;

ll tot,a[maxn],sum[maxn],fac[maxn];

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i],sum[i]=a[i]+sum[i-1];
    }
    tot=sum[n];
    if(tot==1){
        cout<<-1;
        return 0;
    }
    if(tot%2==0){
        fac[++fac[0]]=2;
        while(tot%2==0) tot>>=1LL;
    }
    for(ll i=3;i*i<=tot;i+=2){
        if(tot%i==0){
            fac[++fac[0]]=i;
            while(tot%i==0) tot/=i;
        }
    }
    if(tot!=1){
        fac[++fac[0]]=tot;
    }
    ll ans=1e18+7,tmp,k;
    for(int i=1;i<=fac[0];++i){
        tmp=0,k=fac[i];
        for(int j=1;j<=n;++j){
            tmp+=min(sum[j]%k,k-sum[j]%k);
        }
        ans=min(tmp,ans);
    }
    cout<<ans;
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据