C++14(g++5.4) 解法, 执行用时: 347ms, 内存消耗: 23272K, 提交时间: 2020-06-08 18:09:50

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll a[N],s[N],avg,sum;
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	avg=sum/n;
	for(int i=1;i<n;i++)
	s[i]=s[i-1]+a[i]-avg;
	sort(s,s+n);
	ll res=0;
	for(int i=0;i<n;i++)
	{
		res+=abs(s[i]-s[n/2]);
	 } 
	 printf("%lld\n",res);
	return 0;
}

C++ 解法, 执行用时: 203ms, 内存消耗: 8244K, 提交时间: 2022-04-29 08:38:59

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