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; }
上一篇: 扫地阿姨犀利啊
推荐阅读
-
小米9新增Game Tubro游戏模式:骁龙855智能无卡顿
-
CF341E Candies Game
-
cf1056B. Divide Candies(数论 剩余系)
-
任天堂将推出专利手机壳 一秒将手机变成Game Boy!
-
Ethereum Game通过区块链使游戏参与者实现共赢
-
hdu-1338 game predictions(贪心题)
-
《游戏引擎构架Game Engine Architecture》略读笔记
-
kuangbin专题 专题一 简单搜索 Fire Game FZU - 2150
-
博弈论入门 Bash 、Nim 、Wythoff's Game结论及c++代码实现
-
POJ2505 A multiplication game(博弈)