526互联

牛客练习赛113 D

发布时间 2023-07-10 00:51:09作者: wuyoudexian

D. 小红的数组操作(hard version)

D-小红的数组操作(hard version)_牛客练习赛113 (nowcoder.com)

题意

给定一个序列，可以进行若干次以下操作
1. 选择一个元素，花费\(p\)，使其加\(x\)。
2. 选择一个元素，花费\(q\)，使其减\(y\)。

使得若干次操作后，序列的平均数为一个整数，求最小代价。若无解，输出-1

思路

枚举减\(y\)的次数，然后解同余方程算出需要加\(x\)的次数，即可求出最小的代价。

代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        ll d = exgcd(b, a % b, y, x);
        y -= (a / b) * x;
        return d;
    }
}

bool minx(ll a, ll b, ll c, ll &x, ll &y) {
    ll d = exgcd(a, b, x, y);
    if(c % d != 0) return false;
    x *= c / d;
    y *= c / d;
    x = (x % (b / d) + b / d) % (b / d);
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, p, x, q, y;
    cin >> n >> p >> x >> q >> y;

    ll sum = 0;
    for(int i = 0, tmp; i < n; i++) {
        cin >> tmp;
        sum += tmp;
    }
    sum %= n;

    ll ans = LLONG_MAX;
    for(ll i = 0; i < n; i++) {
        ll b = (n - (sum - i * y) % n + n) % n;
        ll a = 0, k = 0;
        if(minx(x, n, b, a, k)) {
            ans = min(ans, a * p + i * q);
        } 
    }

    if(ans == LLONG_MAX) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}