【题解】UVa P11300 【Spreading the Wealth】

这题其实就是环形均分纸牌,然后就变成了找中位数的问题。


#include<cstdio>
#include<algorithm>

namespace OI{
    using std::sort;
}
using namespace OI;

typedef long long int64;
const int MAXN = 1000000 + 6;
int64 A[MAXN],C[MAXN],tot,M;

inline int abs(int a){
    return a >= 0 ? a : -a;
}

int main(){
    int n;
    while(scanf("%d",&n) == 1){
        tot = 0;
        for(int i = 1;i <= n;i++){
            scanf("%lld",&A[i]);
            tot += A[i];
        }
        M = tot / n;
        C[0] = 0;
        for(int i = 1;i < n;i++){
            C[i] = C[i - 1] + A[i] - M;
        }
        sort(C,C + n);
        int64 x1 = C[n / 2],ans = 0;
        for(int i = 0;i < n;i++){
            ans += abs(x1 - C[i]);
        }
        printf("%lld\n",ans);
    }
    
    return 0;
}