牛客练习赛113 D 小红的数组操作(hard version)

题目要求求出最小的总代价使得平均数为整数，转换式子可得实际就是求出a,b使得(a*x-b*y+sum)%n==0且a*p+b*q要最小，平均值的为sum/n,因此对sum进行操作使其成为n的倍数即可

(a*x-b*y+sum)%n==0

=>((a*x+sum)%n-b*y%n)%n==0

因为(a*x+sum)%n<n,b*y%n<n,因此要想二者差求余数为0一定为(a*x+sum)%n=b*y%n，又因为对于任意倍数的x来说对n取余的余数个数最多不超过n

因此我们先预处理求得所有(a*x+sum)%n的最小花费然后再遍历b*y%n判断是否有对应的a求所有的最小花费

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,p,x,q,y;
map<ll,ll> f;
void solve(){
    ll sum=0;
    cin>>n>>p>>x>>q>>y;
    for(int i=1;i<=n;i++){
        int u;
        cin>>u;
        sum+=u;
    }
    for(int i=0;i<n;i++){
    	if(!f[(i*x%n+sum%n)%n])//注意求最小花费，因为由小到大枚举因此第一次枚举到的一定为最小的
        f[(i*x%n+sum%n)%n]=(i+1)*p;//加一是为了让所有对应的花费都大于0好判断
    }
    ll res=1e18;
    for(int i=0;i<=n;i++){
        int u=i*y%n;
        if(f[u]>0){
            res=min(res,f[u]+i*q-p);//这里要对应的减去1个p
        }
    }
    if(res==1e18) cout<<-1;
    else cout<<res;
    
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}