注：本题解无 AI 生成。

1.思路

1-1.总重量的确定

我们考虑贪心。

为了使选择的大糖果数最多，我们可以让拥有糖果数最少的人全拿大糖果，这样能使总重量最大，从而使别的人有更多操作空间。

1-2.确定总数

现在确定了总重量，如何快速确定

N

个人的大糖果总数呢？

记上文求出的总重量为

w

。设第

i(1 \le i \le N)

个人拥有大糖果

m

个，则他拥有小糖果

A_i - m

个。由于大糖果重量为

Y

，小糖果重量为

X

，可列出等式：

mY + (A_i - m)X = w

去括号，得：

mY + A_iX - mX = w

m(Y - X) + A_iX = w

m(Y - X) = w - A_iX

\because Y > X

\therefore Y - X \not = 0

\therefore m = \dfrac{w - A_iX}{Y - X}

到这里，我们就得到了

\mathcal O(1)

求

1

个人拥有大糖果数量的公式，直接将每个

A_i

代入求值，再相加即可。

1-3.无解判定

如何判断无解？

我们注意到，上文的

m

必须为整数，因为糖果不可能有小数个，所以第一种无解情况即为：

m

不是整数。

到这里，有的同学会思考：那为什么不能缩小总重量

w

，万一有其他可能的方案呢？

我们感性理解下，如果要缩小

w

，那么就需要减少一个大糖果，增加一个小糖果，

w

将减少

Y - X

，而求

m

的公式中除式正是

Y - X

。所以，就算减少

w

，也不能使

m

变为整数，同样无解。

还有一种无解情况：

w - A_iX < 0

，此时说明最大总重量比某个人全拿小糖果的重量还少，无解。

总结一下，无解情况共两种：

$(w - A_iX) \bmod (Y - X) \not = 0$ ；
$w - A_iX < 0$ 。

2.代码

注：代码仅供参考。

CPP

123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>
using namespace std;
const int max_n=2e5+2;
int n,x,y,a[max_n];
int mina=1e9+1; //数组最小值 
long long w; //总价值
long long ans; //答案 
int cha; //记录 y-x 
inline int read(){ //快读
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
int main(){
	n=read(),x=read(),y=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		mina=min(mina,a[i]);
	}
	w=1ll*mina*y,cha=y-x; 
	for(int i=1;i<=n;i++){
		long long noww=w-1ll*a[i]*x;
		if(noww%cha||noww<0){ //除不尽或小于 0，说明无解 
			puts("-1");
			return 0;
		}
		ans+=(noww/cha);
	}
	printf("%lld\n",ans); 
	return 0;
}

题解：AT_abc432_c [ABC432C] Candy Tribulation

文章操作