欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

CF341E Candies Game

程序员文章站 2023-09-07 16:26:53
题意 有$n$个盒子,第$i$个盒子里面有$a_i$个糖果。每次选择两个盒子$i,j$,假设$a_i \le a_j$。然后从第$j$个盒子中拿出$a_i$个糖果,放到第$i$个盒子里面(显然,如果$a_i=a_j$,那么第$j$个盒子会变成空的)。你可以这样操作任意多次。要求最后只有$2$个盒... ......

题目链接

题意

\(n\)个盒子,第\(i\)个盒子里面有\(a_i\)个糖果。每次选择两个盒子\(i,j\),假设\(a_i \le a_j\)。然后从第\(j\)个盒子中拿出\(a_i\)个糖果,放到第\(i\)个盒子里面(显然,如果\(a_i=a_j\),那么第\(j\)个盒子会变成空的)。你可以这样操作任意多次。要求最后只有\(2\)个盒子里面有糖果。输出方案。如果无论如何操作也无法满足条件,输出"\(-1\)"

思路

考虑当前有\(3\)个盒子\(i,j,k (a_i\le a_j\le a_k)\)。其实可以发现,一定能够使得这三个盒子中的某个变为空。操作如下:
\(t = \lfloor\frac{a_j}{a_i}\rfloor\)。对于第\(i\)次操作,如果\(t\)的二进制中第\(i-1\)位为\(1\)的话,就操作\(a_i,a_j\), 否则操作\(a_i,a_k\)。然后\(a_j\)就会变成\(a_j\%a_i\)。然后再重新排序,重复上面的操作,直到有一个盒子变为空.
所以只要每次选出三个盒子进行上面的操作就行了。

代码

/*
* @author: wxyww
* @date:   2019-02-13 10:00:24
* @last modified time: 2019-02-13 10:17:54
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 1000010;
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*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int x,id;
}a[n],ans[n];
int ansjs;
bool cmp(node x,node y) {
    if(x.x != y.x)
    return x.x > y.x;
    return x.id < y.id;
}
void solve() {
    int k = a[2].x / a[3].x;
    while(k) {
        if(k & 1) {
            a[2].x -= a[3].x;
            a[3].x <<= 1;
            // printf("%d %d\n",a[])
            ans[++ansjs].x = a[3].id,ans[ansjs].id = a[2].id;
        }
        else {
            a[1].x -= a[3].x;
            a[3].x <<= 1;
            ans[++ansjs].x = a[3].id,ans[ansjs].id = a[1].id;
        }
        k >>= 1;
    }
}
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) a[i].id = i,a[i].x = read();
    sort(a + 1,a + n + 1,cmp);
    if(!a[2].x) {
        puts("-1");return 0;
    }
    while(a[3].x) {
        // printf("%d %d %d\n",a[1].id,a[2].id,a[3].id);
        solve();
        sort(a + 1,a + n + 1,cmp);
    }
    printf("%d\n",ansjs);
    for(int i = 1;i <= ansjs;++i) printf("%d %d\n",ans[i].x,ans[i].id);
    return 0;
}