【枚举+exgcd】牛客练习赛33 C D

Love The Way You Lie 2024-03-17 17:40 103阅读 0赞

[牛客练习赛113\_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛\_牛客竞赛OJ (nowcoder.com)][113_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]

题意：

![5c9c20c4e252472298849f4e9ac0047f.png][]

思路：

首先要使平均数是整数，说明sum是N的倍数，即要使sum%N=0

问题就是经过若干次操作的最少代价，可以使sum%N=0

那就去考虑模N意义下的sum

easy版本一般是枚举，我们去考虑枚举

注意到减y的次数不会超过N，因此我们去枚举减y的次数，然后去计算加x的次数

如果x=1，那么加x的次数可以直接计算

但是如果x!=1，那么需要exgcd

![c2f4bf122f2946fc80eb42d861b38177.jpeg][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N,P,X,Q,Y;
    int a[mxn];
    
    void solve(){
        cin>>N>>P>>X>>Q>>Y;
        int sum=0;
        for(int i=1;i<=N;i++){
            cin>>a[i];
            sum+=a[i];
        }
        sum%=N;
        int ans=1e18;
        for(int i=0;i<=N;i++){
            ans=min(ans,i*Q+(N-((sum-i*Y)%N+N)%N)%N*P);
        }
        cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    int N,p,x,q,y,j,k;
    int sum=0,ans=1e18;
    int c[mxn];
    
    int exgcd(int a,int b,int &x,int &y){
        if(!b){
            x=1;y=0;
            return a;
        }
        int d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;
    }
    void solve(){
        cin>>N>>p>>x>>q>>y;
        for(int i=1;i<=N;i++){
            cin>>c[i];
            sum+=c[i];
        }
        for(int i=0;i<N;i++){
            int D=exgcd(x,N,j,k);
            if(((i*y-sum)%D+D)%D!=0) continue;
            else{
                j=j*(i*y-sum)/D;
                int r=N/D;
                j=(j%r+r)%r;
                if(j<0) continue;
                ans=min(ans,j*p+i*q); 
            }
        }
        if(ans==Inf) cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[113_ACM_NOI_CSP_CCPC_ICPC_OJ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/60282
[5c9c20c4e252472298849f4e9ac0047f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/12a766aaee104fd48efc7458b94a78f8.png
[c2f4bf122f2946fc80eb42d861b38177.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9ca832280dc84111be07471093795419.png