当前位置：首页 > news >正文

打卡信奥刷题（3196）用C++实现信奥题 P8103 「LCOI2022」 Cow Merger

news 2026/5/1 23:03:55

P8103 「LCOI2022」 Cow Merger

题目背景

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

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

题目描述

Farmer John 的农场里本来有nnn个牛棚，第iii个牛棚里住着aia_iai只牛。

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

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

输入格式

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

对于第ttt组数据:

第2t2t2t行包含一个整数nnn。

第2t+12t+12t+1行包含nnn个整数，第iii个整数为aia_iai。

输出格式

对于每组数据：

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

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

接下来mmm行，每行输出两个数iii和jjj（注意操作时应满足ai≥aja_i \ge a_jai≥aj）。

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

输入输出样例 #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%100\%100%的数据，1≤T≤51 \leq T \leq 51≤T≤5，1≤n≤1051 \leq n \leq 10^51≤n≤105，0≤ai≤1090 \leq a_i \leq 10^90≤ai≤109。

C++实现

#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;longlongn,i,t,k,a[100001],b,c,d,m,l[1000001],r[1000001];intmain(){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;}}elsed=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]);}}return0;}