Candy delivery (Mathematics)

This problem is essentially a mathematical problem , Presuppose xi In the best case i A child gave it to No i-1 The number of sweets for a child (xi A negative number means the i-1 A child gave the first i A child candy ), A special case ： When i by 1 when , Default i-1=n, That is to say x1 It means the first one 1 A child gave it to No n The number of sweets for a child . Then our The result is all xi The sum of the absolute values of （ The number of candy delivered is the final price ）, The title has given the number of sweets each child had at the beginning ai, Let the number of sweets each child finally gets be mid, So the first i The final number of sweets for children mid Depends on the number of sweets you have at the beginning ai And he gave No i-1 The number of sweets for a child xi And the first i+1 A child gave him the number of sweets xi+1, That is to say mid=ai-xi+x(i+1), Simplify to x(i+1)-xi=mid-ai, From this formula, we can get

(1)  x2-x1=mid-a1

(2)  x3-x2=mid-a2

……

(n-1)  xn-x(n-1)=mid-a(n-1)

Combining the above formulas, we get

(1)+(2) have to x3-x1=2*mid-(a2+a1)

(1)+(2)+(3) have to x4-x1=3*mid-(a3+a2+a1)

……

(1)+(2)+……+(n-1) have to xn-x1=(n-1)*mid-(a(n-1)+a(n-2)+……+a1)

Move the terms of the merged formula to get ：

x2=x1-(a1-mid)

x3=x1-((a2+a1)-2*mid)

x4=x1-((a3+a2+a1)-3*mid)

……

xn=x1-((a(n-1)+……+a2+a1)-(n-1)*mid)

Again because x1=x1-0

Our final result is xi The sum of the absolute values of , It's easy to think of the distance formula when you see the formula after the term shift above , So our result is One point to 0,(a1-mid),((a2+a1)-2*mid),……,((a(n-1)+……+a2+a1)-(n-1)*mid) The minimum value of the sum of the distances of these points , This can be transformed into the problem of warehouse location , Directly take a median for calculation , Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1000003;
long long a[N],s[N];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	long long mid=s[n]/n;
	for(int i=1;i<=n;i++)
		s[i]-=i*mid;
	sort(s,s+n);
	long long ans=0;
	for(int i=0;i<n;i++)
		ans+=abs(s[i]-s[n/2]);
	printf("%lld",ans);
	return 0;
}