abc432_C

Candy Tribulation (abc432 c)

你拥有无限供应的两种糖果：小糖果和大糖果。一颗小糖果的重量是X克，一颗大糖果的重量是Y克，且大糖果比小糖果重（即X < Y）。

有N个孩子，编号从1到N。

你决定分发糖果，需满足以下条件：

• 对于 i=1,…,N，孩子i总共收到恰好Ai颗两种类型的糖果。
• 分发给这N个孩子的糖果总重量都相等。

请判断是否存在满足条件的分发方法。如果存在，请找出分发出的大糖果数量的最大可能值。

约束条件：

• 2 ≤ N ≤ 2×10^5
• 1 ≤ A_i ≤ 10^9
• 1 ≤ X < Y ≤ 10^9
• 所有输入值均为整数。

---

对于每个孩子 i ：

• 设得到 S_i 颗小糖果， L_i 颗大糖果，总重量为 W
• 始终满足：S_i + L_i = A_i 和 W = X ⋅ S_i + Y ⋅ L_i

$$ \begin{aligned} S_i &= A_i - L_i \\ W &= X\cdot (A_i - L_i) + Y\cdot L_i \\ W &= (Y - X)\cdot L_i + X\cdot A_i \\ L_i &= \frac{W-X\cdot A_i}{Y-X} \end{aligned} $$

由于 L_i 必须是整数，所以 (W − X ⋅ A_i) 必须能被 (Y − X)整除，这同时也意味着对于任意孩子，都必须满足 X ⋅ A_i 对 (Y − X) 取模必须相同

▶

code

long long bias = Y - X;
long long R = (X % bias * (arr[0] % bias)) % bias;
for (int i = 1; i < N; i++){
    long long cur = (X % bias * (arr[i] % bias)) % bias;
    if (cur != R){
        cout << -1;
        return 0;
    }
}

由于 L_i 必须是非负整数且不超过 A_i，于是有以下约束： $$ \begin{aligned} L_i \ge 0 &\Rightarrow W-X\cdot A_i \ge 0 \Rightarrow W\ge X\cdot A_i \\ L_i \le A_i &\Rightarrow W-X\cdot A_i \le A_i\cdot (Y-X) \\ &\Rightarrow W \le A_i\cdot Y \end{aligned} $$ 所以在程序中要记录 max(A_i ⋅ X) 和 min(A_i ⋅ Y)，并判断是否存在合法的 W

▶

code

long long minW = 0, maxW = 2e18;
for (int i = 0; i < N; i++){
    minW = max(minW, arr[i] * X)
    maxW = min(maxW, arr[i] * Y);
}
if (minW > maxW){
    cout << -1;
    return 0;
}

接着要找到最大且合法的 W ，由 (W − X ⋅ A_i) 必须能被 (Y − X)整除可知， W ≡ R(mod Bias)，其中 R 是 X ⋅ A_i 对 (Y − X) 取模，所以 W 可以表示为 R + k ⋅ Bias 同时满足 R + k ⋅ Bias ≤ maxW，解出 $k\le \lfloor \frac{maxW-R}{Bias} \rfloor$， 这样就能得到需要的 W

▶

code

if (maxW - R >= 0){
    long long k = (maxW - R) / Bias;
    W = R + k * bias;
}

最后计算答案即可

完整代码：

▶

code

#include <algorithm>
#include <ios>
#include <iostream>
#include <vector>
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    long long N, X, Y;
    std::cin >> N >> X >> Y;
    std::vector<long long> arr(N);
    for (int i = 0; i < N; i++)
        std::cin >> arr[i];
    long long bias = Y - X;
    long long R = (X % bias * (arr[0] % bias)) % bias;
    for (int i = 1; i < N; i++){
        long long cur = (X % bias * (arr[i] % bias)) % bias;
        if (cur != R){
            std::cout << "-1";
            return 0;
        }
    }
    long long minW = 0, maxW = 2e18, W;
    for (int i = 0; i < N; i++){
        minW = std::max(minW, arr[i] * X);
        maxW = std::min(maxW, arr[i] * Y);
    }
    if (minW > maxW){
        std::cout << "-1";
        return 0;
    }
    if (maxW - R >= 0){
        long long k = (maxW - R) / bias;
        W = R + k * bias;
    }
    if (W < minW) {
        std::cout << "-1";
        return 0;
    }
    long long sum = 0;
    for (int i = 0; i < N; i++)
        sum += (W - X * arr[i]) / bias;
    std::cout << sum;
    return 0;
}