题解：AT_abc432_c [ABC432C] Candy Tribulation

ryf2011 · 2025-11-23 10:53:59 · 题解

注：本题解无 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，此时说明最大总重量比某个人全拿小糖果的重量还少，无解。

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

2.代码

注：代码仅供参考。

#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;
}