题解 CF341E 【Candies Game】

发表于 更新于 阅读次数： Waline：
CF341E 【Candies Game】题解。

这个题目实际上就是一个贪心

注意到合并的原则是当$ a_{i} \leq a_{j} $时才能合并，所以我们必须把小的先合并了，不然到后面越合并越大，小的就并不了了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#define swap(x,y) x^=y^=x^=y
#define set(x) ans1[++m]=p1,ans2[m]=x,a[x]-=a[p1],a[p1]<<=1
int i,j,n,m,p1,p2,p3,a[1001],ans1[100000],ans2[100000];
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;scanf("%d",a+i++));
	for(p2=1,p3=2,i=3;i<=n;++i)
		for(p1=i;;){
			if(a[p1]>a[p2])swap(p1,p2);
			if(a[p2]>a[p3])swap(p2,p3);
			if(a[p1]>a[p2])swap(p1,p2);//交换，保证顺序
			if(a[p1]==0)break;//空了
			for(j=a[p2]/a[p1];j;j>>=1)if(j&1)set(p2);else set(p3);//模拟合并
		}
	if((a[p1]==0)+(a[p2]==0)+(a[p3]==0)!=1)puts("-1");//判断不可行
	else for(printf("%d\n",m),i=1;i<=m;++i)printf("%d %d\n",ans1[i],ans2[i]);//输出
	return 0;
}