CF341E Candies Game解题报告

解题报告

CF341E Candies Game解题报告：

更好的阅读体验

题意

• 给定$n$个盒子，第$i$个盒子有$a_i$颗糖；
• 每次可以选择两个盒子$i,j(a_i\leqslant a_j)$，使得盒子$j$中取$a_i$颗糖放入盒子$i$；
• 需要让最后只剩两个盒子有糖，求操作方案，如果无解输出$-1$。
• 数据范围：$3\leqslant n\leqslant 10^3,0\leqslant \sum a_i\leqslant 10^6$。

分析

有点没看懂原来的题解在说什么。

首先特判只有零/一个盒子有糖的情况，输出$-1$。

对于三个非空盒子$x,y,z(a_x\leqslant a_y\leqslant a_z)$，我们可以通过若干次操作，使得操作后的$x',y',z'(a_{x'}\leqslant a_{y'}\leqslant a_{z'})$中$a_{x'}<a_x$。这样只要进行足够多次操作，就可以使得某一个盒子的糖数量归零。

设$k=\lfloor\frac{a_y}{a_x}\rfloor$，那么有$a_y=k\times a_x+t$（$0<t<a_x$）。

我们用二进制表示出$k$，然后枚举$i$从$0$到$k$的最高位$\omega_k$，对于$k$的第$i$位进行下列操作：

• 如果$k$的第$i$位为$1$，那么进行一次$(x,y)$操作，则$k$这一位的$1$会被当前的$2^{i-1}\times a_x$夺去（因为在这一次操作前$x$进行了$i-1$次操作，每一次操作都可以让$a_x$乘$2$）。
• 如果$k$的第$i$位为$0$，那么进行一次$(x,z)$操作，则不难发现每一次操作都可以让$a_x$乘$2$。（因为每次$(x,z)$操作的位数都低于$\omega_k$，所以$a_z$需要付出的$a_x$数量一定是低于$k$的，那么就一定可以保证$a_z$每次操作前都比$a_x$大）。

这样，经过若干次操作后，$a_y$的值会变成$t$，我们对$x,y,z$重新排序，那么一定有$a_{x'}<a_x$。

经过若干次操作，我们便可以让某个盒子里的糖数归零。那么我们对非空的三个盒子做若干次操作就可以只剩两个盒子。

然后分析操作次数：最劣的情况下，对于每个盒子都要进行一次这样的操作，而每次操作都会进行若干轮，轮数可以通过类似辗转相除的复杂度证明，发现轮数和执行$\gcd(a,b,c)$的操作数是等价的，而很显然对于操作$p$轮需要的$a,b,c$最小值$f_p$的增长速度是快于斐波那契数列的，也就是说轮数是$O(\log \max\{a_i\})$的，而每一轮的操作数为$\omega_k$，最大也是$O(\log\max\{a_i\})$的。

因此，该算法的时间复杂度和操作数均为$O(n\log^2\max\{a_i\})$，足够通过本题。

代码

#include<stdio.h>
const int maxn=1005,maxk=405;
int n,zero,anss,p1,p2,p3;
int ans[maxn*maxk][2];
struct candy{
    int v,p;
}c[maxn];
inline void chk(candy &a,candy &b){
    candy tmp;
    if(a.v>b.v)
        tmp=a,a=b,b=tmp;
}
inline void move(candy &a,candy &b){
    anss++,ans[anss][0]=a.p,ans[anss][1]=b.p;
    b.v-=a.v,a.v<<=1;
}
void merge(candy a,candy b,candy c,candy &res1,candy &res2){
    chk(a,b),chk(a,c),chk(b,c);
    if(a.v==0){
        res1=b,res2=c;
        return ;
    }
    int k=b.v/a.v;
    while(k){
        if(k&1)
            move(a,b);
        else move(a,c);
        k>>=1;
    }
    merge(a,b,c,res1,res2);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i].v),c[i].p=i;
        zero+=c[i].v==0;
    }
    if(n-zero<2){
        puts("-1");
        return 0;
    }
    for(p1=1;p1<=n&&c[p1].v==0;p1++);
    for(p2=p1+1;p2<=n&&c[p2].v==0;p2++);
    for(p3=p2+1;p3<=n&&c[p3].v==0;p3++);
    while(p3<=n){
        candy tmp1,tmp2;
        merge(c[p1],c[p2],c[p3],tmp1,tmp2);
        c[p2]=tmp1,c[p3]=tmp2;
        p1=p2,p2=p3;
        for(p3++;p3<=n&&c[p3].v==0;p3++);
    }
    printf("%d\n",anss);
    for(int i=1;i<=anss;i++)
        printf("%d %d\n",ans[i][0],ans[i][1]);
    return 0;
}