【题解】糖果传递

题目链接

解题思路

设A为原数组, $X_i$ 为从i向i-1传递了 $X_i$ 个糖果。

$$ A_1+X_2-X_1=ave \\A_2+X_3-X_2=ave \\. \\. \\. \\A_i+X_{i+1}-X_i=ave \\A_n+X_1-X_n=ave \\ $$

$$ X_2=X_1+ave-A_1 \\X_3=X_2+ave-A_2=X_1+ave-A_1+ave-A_2=X_1+2*ave-\sum^{2}_{i=1}A_i \\X_i=X_1+(i-1)ave-\sum^{i-1}_{j=1}A_j \\X_1=X_1+n*ave-\sum^{n}_{i=1}A_i $$

$$ 设 \\C_i=\sum^{i}_{j=1}A_j-ave*i \\X_2=X_1-C_1 \\X_i=X_1-C_{i-1} $$

$$ |X_1|+|X_2|+|X_3|+...+|X_n| \\=|X_1-C_n|+|X_1-C_1|+|X_1-C_2|+...+|X_1-C_n-1| $$

所以根据绝对值的几何意义, $X_1$ 是C中的中位数即可。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
long long c[1000005];
int main(){
    int n;
    cin>>n;
    long long ave=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ave+=a[i];
    }
    ave/=n;
    for(int i=1;i<=n;i++){
        c[i]=c[i-1]+a[i]-ave;
    }
    sort(c+1,c+1+n);
    long long ans=0;
    long long mid=c[(n+1)/2];//mid即最优的第一个的x_1 
    for(int i=1;i<=n;i++){
        ans+=abs(mid-c[i]);
    }
    printf("%lld",ans);
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/698/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者