122题 糖果传递
有用到中位数
代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
const int manx = 1e7;
int n,a[manx],sum[manx],ave,ans;
main(){
n = read();
for(int i = 1;i <= n; i++){
a[i] = read();
ave += a[i];
}
ave /= n;
for(int i = 1;i <= n; i++) a[i] -= ave;
for(int i = 1;i <= n; i++){
sum[i] = sum[i - 1] + a[i];
}
sort(sum+1,sum+1+n);
int t = sum[(n+1)>>1];
for(int i = 1;i <= n; i++) ans += abs(t - sum[i]);
cout<<ans;
}