P8103 「LCOI2022」 Cow Merger

题目背景

Bessie 来到她的新家之后，Farmer John 突然意识到自己农场的大小不够了！

所以，Farmer John 需要把所有的奶牛合并到一个牛棚里。

题目描述

Farmer John 的农场里本来有 $n$ 个牛棚，第 $i$ 个牛棚里住着 $a_i$ 只牛。

我们定义一次合并 $i,j(a_i\ge a_j)$ 两个牛棚的操作为：从 $i$ 号牛棚中拿出 $a_j$ 头牛，放入 $j$ 号牛棚中。如果在合并结束后 $a_i=0$，那么可以看做 $a_i$ 被合并了，接下来的操作也与 $a_i$ 无关。

由于时间不够了，他决定最多你 $1$ 秒的时间。

输入格式

第一行包含一个整数 $T$，表示数据组数。

对于第 $t$ 组数据:

第 $2t$ 行包含一个整数 $n$。

第 $2t+1$ 行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$。

输出格式

对于每组数据：

如果你发现自己不可能达到目标，输出 NO，否则输出 YES。

接下来一行，输出一个整数 $m$ 表示操作次数。

接下来 $m$ 行，每行输出两个数 $i$ 和 $j$（注意操作时应满足 $a_i\ge a_j$）。

有多解时可输出任意一组解。

输入输出样例 #1

输入 #1

3
4
1 2 3 2
5
3 9 6 18 12
5
2 3 5 7 11

输出 #1

YES
4
3 1
1 2
3 4
2 4
YES
6
2 1
1 2
4 3
2 3
4 5
3 5
NO

说明/提示

【数据范围与约定】

对于 $100\%$ 的数据，$1\le T\le 5$，$1\le n\le 10^5$，$0\le a_i\le 10^9$。

C++实现

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,i,t,k,a[100001],b,c,d,m,l[1000001],r[1000001];
int main(){
	scanf("%lld",&t);
	for(k=1;k<=t;k=k+1)	{
		scanf("%lld",&n);b=0;c=0;d=0;
		for(i=1;i<=n;i=i+1)		{
			scanf("%lld",&a[i]);
			b=__gcd(b,a[i]);
		}
		for(i=1;i<=n;i=i+1)a[i]=a[i]/b;
		for(i=1;i<=n;i=i+1)c=c+a[i];
		for(i=1;;i=i*2)		{
			if(i>c){d=1;break;}
			if(i==c)break;
		}
		if(d==1){printf("NO\n");continue;}
		else		{
			printf("YES\n");m=0;
			while(1)			{
				b=0;c=0;d=0;
				for(i=1;i<=n;i=i+1)		{
					if(a[i]%2==1)		{
						c=c+1;
						if(c==2)	{
							m=m+1;c=0;
							if(a[i]>a[d]){l[m]=i;r[m]=d;a[i]=a[i]-a[d];a[d]=a[d]*2;}
							else {l[m]=d;r[m]=i;a[d]=a[d]-a[i];a[i]=a[i]*2;}
						}
						else d=i;
					}
				}
				if(c==1)break;
				for(i=1;i<=n;i=i+1)b=__gcd(b,a[i]);
				for(i=1;i<=n;i=i+1)a[i]=a[i]/b;
			}
			printf("%lld\n",m);
			for(i=1;i<=m;i=i+1)printf("%lld %lld\n",l[i],r[i]);
		}
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容