题解：AT_abc432_c [ABC432C] Candy Tribulation

· · 题解

来补一篇题解。

赛时仅过 AB，是不是没救了。

首先，考虑全部分配小糖果，即第 i 个小孩共有 A_i \times X 克的糖果。那么，此时必须两两重量差对 Y-X 取模结果为 0 才有可能使所有小孩获得糖果的总克数相等，因为用 k 颗大糖果替换 k 颗小糖果能产生 k \times (Y-X) 的贡献。显然，判断时仅需判断相邻两个小朋友即可。

然后，考虑将所有小孩的糖果重量同步为目前所有小孩中糖果重量的最大值。如全部替换仍旧达不到，那么无解。然后，找到所有小孩中小糖果数量的最小值 minn，显然，所有人可以再次将 minn 颗大糖果替换 minn 颗小糖果。

#include<bits/stdc++.h>
#define ll long long
#define ull unsgined ll
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define fi first
#define se second
#define gtc getchar
#define ptc putchar
using namespace std;
const int N=2e5+5;
int n,x,y;
int a[N];
ll b[N];
ll ans;
int minn=1e9;
int main(){
    scanf("%d%d%d",&n,&x,&y);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        b[i]=1ll*a[i]*x;
    }
    for(int i=2;i<=n;i++){
        if((b[i]-b[i-1])%(y-x)){
            puts("-1");
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        ll cnt=(b[n]-b[i])/(y-x);
        if(cnt>a[i]){
            puts("-1");
            return 0;
        }
        ans+=cnt;
        a[i]-=cnt;
        minn=min(minn,a[i]);
    }
    ans+=1ll*minn*n;
    printf("%lld\n",ans);
    return 0;
}

AC 记录。