1 solutions

  • 0
    @ 2022-11-28 13:22:57
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<stdlib.h>
    using namespace std;
    const int N = 1000010;
    typedef long long ll;
    int n;
    ll init[N],c[N];
    //首先,最终每个人的金币数量可以计算出来,它等于金币总数除以人数n,
    //接下来我们用M表示每人最终拥有的金币数。假设在这个过程中,
    //可以设x2表示2号给了1号多少个金币,x3,x4类似。由于是环型,
    //x1指的是1号给了4号多少金币。
    //对于编号为i的人,初始为Ai,则1号,他最终剩余A1-x1+x2=M。
    int main(){
        while(cin>>n){
            ll sum=0;
            for(int i=0;i<n;i++){
                cin>>init[i];
                sum+=init[i];
            }
            ll avg=sum/n;//求出每个人的最终情况 
            c[0]=0;//让c[0]为0,防止c[i-1]出问题 
            for(int i=1;i<n;i++){
                c[i] =c[i-1] + init[i]-avg;//由证明 
            }
            sort(c,c+n);
            ll res = c[n/2],ans=0;//求出中位数 
            for(int i=0;i<n;i++){
                ans = ans+abs(res-c[i]);//由证明 
            }
            cout<<ans<<endl;
        }
        return 0;
    }
    

    image

    • 1

    Information

    ID
    6637
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    6
    Accepted
    3
    Uploaded By