P2512 [HAOI2008]糖果传递

P2512 [HAOI2008]糖果传递

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout<<#x<<':'<<x<<endl;
const int maxn=1e6+100;
ll a[maxn],n;
int main(){
    scanf("%lld",&n);
    vector<ll>vc;ll ave=0;vc.push_back(0);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        ave+=a[i];
    }
    ave/=n;
    for(int i=2;i<=n;i++){
        vc.push_back(vc[i-2]+ave-a[i]);
    }
    sort(vc.begin(),vc.end());//选中位数，即n/2;
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=abs(vc[n/2]-vc[i]);
    }
    printf("%lld
",ans);
    //system("pause");
}