题解 CF341E 【Candies Game】

whiteqwq · 2021-01-25 14:44:48 · 题解

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;
}