题解 | #小红的数组操作(hard version)#

注意到，数组的平均数是一个整数等价于 。

于是题目可以转化为 个点，每个点 和 有一条代价 为 的边， 和 有一条代价 为 的边。问节点 到 的最小代价。

跑最短路即可。

void solve(){
    ll n = read(), p = read(), x = read(), q = read(), y = read();
    ll sum = 0;
    for(ll i=0;i<n;i++){
        sum = (sum + read())%n;
    }
    x %= n;
    y %= n;
    priority_queue<PLL, vector<PLL>, greater<PLL>> pq;
    vector<ll> dis(n+1, INF);
    dis[sum] = 0;
    pq.push({0, sum});
    while(!pq.empty()){
        auto [cost, sum] = pq.top();
        pq.pop();
        if(dis[(sum + x)%n] > cost + p){
            dis[(sum + x)%n] = cost + p;
            pq.push({cost + p, (sum + x)%n});
        }
        if(dis[(sum + n - y)%n] > cost + q){
            dis[(sum + n - y)%n]  = cost + q;
            pq.push({cost + q, (sum + n - y)%n});
        }
    }
    print(dis[0]>=INF?-1:dis[0]);
}

c++ 火车头

// FZANOTFOUND
#include <bits/stdc++.h>
using namespace std;

#define pb push_back 
#define eb emplace_back 
#define fi first
#define se second
#define ne " -> "
#define sep "======"
#define fastio ios::sync_with_stdio(false);cin.tie(0);
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<long long,long long> PLL;
typedef tuple<ll,ll,ll> TLLL;
const ll INF = (ll)2e18+9;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const db PI = 3.14159265358979323;

//io functions
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}  
inline ll read(){ll x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;return x;}  
inline void pt(ll x){if(x<0) putchar('-'),x=-x;if(x>9) pt(x/10);putchar(x%10+'0');}
inline void print(ll x){pt(x), puts("");}
inline void print(PLL x){pt(x.fi), putchar(' '), pt(x.se), putchar('\n');}
inline void print(vector<ll> &vec){for(const auto t:vec)pt(t),putchar(' ');puts("");}
inline void print(const map<ll, ll>& g) {for(const auto& [key, value]:g){cout<<"key: "<<key<<ne<<value<<" ";}puts("");}
inline void print(vector<PLL> &vec){puts(sep);for(const auto v:vec){print(v);}puts(sep);}
inline void print(const map<ll, vector<ll>>& g) {for (const auto& [key, value] : g) { cout << "key: " << key << ne;for (const auto& v : value) {cout << v << " ";}cout << endl;}}

//fast pow
ll ksm(ll a, ll b=MOD-2, ll M=MOD){a%=M;ll res=1;while(b){if(b&1){res=(res*a)%M;}a=(a*a)%M;b>>=1;}return res;}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());//rng()
ull randint(ull l, ull r){uniform_int_distribution<unsigned long long> dist(l, r);return dist(rng);}


void init(){

}

void solve(){

}

int main(){
    init();
    ll t = 1;
    //t = read();
    while(t--){
        solve();
    }
}