题意

有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

思路

把|s[i]-s[k]|求和即可，s[i]是A的前缀和

s[k]为s数组的中位数时，总值最小

Code

#include<bits/stdc++.h> using namespace std; int a[1000005]; int sum[1000005]; int main() { long long n=0,t=0; scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); t += a[i]; } for (int i = 2; i <= n; i++) sum[i] = sum[i - 1] - a[i] + t / n; long long ans = 0; sort(sum + 1, sum + 1 + n); int mid = sum[n / 2]; for (int i = 1; i <= n; i++) { ans += abs(sum[i] - mid); } printf("%lld\n", ans); return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10124639.html

相关资源：JAVA上百实例源码以及开源项目