This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

The original address

Commit 10.41K through 4.81K time limit 1.00s memory limit 125.00MBCopy the code

Topic describes

There are nn children sitting in a circle, and each of them has aiA_iai sweets. Each person can only pass candy to the right or left two people. Each candy pass costs 111.

Input format

Number of children, NNN, NNN line aia_iai.

The output format

Find the minimum cost of making sweets equally available to all.

Input and output examples

Enter the # 1

4
1
2
5
4
Copy the code

Output # 1

4
Copy the code

Note/hint for 100%100\%100% data n≤ 106N \le 10^6n≤106.

Ideas:

Let the original number of sweets owned by each person be AiA_iAi, the number passed to the right each time is XiX_iXi (− XI-x_I −Xi to the left), and the average number of sweets is Avgavgavg.

There are


The original – To the right + It came in from the left = The average Original – outgoing to the right + incoming to the left = average

namely


A i – X i + X i + 1 = a v g A_i-X_i+X_{i+1}=avg

Simultaneous equations


{ A 1 – X 1 + X 2 = a v g A 2 – X 2 + X 3 = a v g … A n – 1 – X n – 1 + X n = a v g A n – X n + X 1 = a v g \left\{ \begin{aligned} A_1-X_1+X_{2}&=avg \\ A_2-X_2+X_{3}&=avg \\ \cdots \\ A_{n-1}-X_{n-1}+X_{n}&=avg \\ A_n-X_n+X_{1}&=avg \\ \end{aligned} \right.

tidy


{ – X 1 + X 2 = a v g – A 1 – X 2 + X 3 = a v g – A 2 … – X n – 1 + X n = a v g – A n – 1 X 1 – X n = a v g – A n \left\{ \begin{aligned} -X_1+X_{2}&=avg-A_1 \\ -X_2+X_{3}&=avg-A_2 \\ \cdots \\ -X_{n-1}+X_{n}&=avg-A_{n-1} \\ X_{1}-X_n&=avg-A_n \\ \end{aligned} \right.

Its augmented matrix


B = ( A       Beta. ) = [ – 1 1 0 … 0 0 a v e – A 1 0 – 1 1 … 0 0 a v e – A 2 ⋮ ⋱ ⋮ ⋮ 0 0 0 … – 1 1 a v e – A n – 1 1 0 0 … 0 – 1 a v e – A n ] B=(A \; \; \beta)= \left[ \begin{array}{cccccc|c} -1 & 1 & 0 & \cdots & 0 & 0 & ave-A_1\\ 0 & -1 & 1 & \cdots & 0 & 0 & ave-A_2\\ \vdots & & \ddots& & & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & -1 & 1 & ave-A_{n-1}\\ 1 & 0 & 0 & \cdots & 0 & -1 & ave-A_{n}\\ \end{array} \right]

To minimize the row


[ 1 0 0 … 0 – 1 ( ∑ i = 1 n – 1 A i ) – ( n – 1 ) a v e 0 1 0 … 0 – 1 ( ∑ i = 2 n – 1 A i ) – ( n – 2 ) a v e ⋮ ⋱ ⋮ ⋮ 0 0 0 … 1 – 1 A n – 1 – a v e 0 0 0 … 0 0 0 ] \left[ \begin{array}{cccccc|c} 1 & 0 & 0 & \cdots & 0 & -1 & (\sum_{i=1}^{n-1}A_i)-(n-1)ave\\ 0 & 1 & 0 & \cdots & 0 & -1 & (\sum_{i=2}^{n-1}A_i)-(n-2)ave\\ \vdots & & \ddots& & & \vdots & \vdots\\ 0 & 0 & 0 & \cdots & 1 & -1 & A_{n-1}-ave\\ 0 & 0 & 0 & \cdots & 0 & 0 & 0\\ \end{array} \right]

The solution of the system is


{ X 1 = X n + ( ∑ i = 1 n – 1 A i ) – ( n – 1 ) a v e X 2 = X n + ( ∑ i = 2 n – 1 A i ) – ( n – 2 ) a v e ⋮ X n – 1 = X n + A n – 1 – a v e X n = X n ∈ R \left\{ \begin{aligned} X_1&=X_n+(\sum_{i=1}^{n-1}A_i)&-(n-1)ave\\ X_2&=X_n+(\sum_{i=2}^{n-1}A_i)&-(n-2)ave\\ &\qquad \qquad \qquad \vdots \\ X_{n-1}&=X_n+A_{n-1}&-ave\\ X_n&=X_n&\in{\Bbb R}\\ \end{aligned} \right.

Now require ∑ I = 1 n ∣ Xi ∣ \ sum_ {I = 1} ^ {n} | X_i | ∑ I = 1 n ∣ Xi ∣ minimum value

Observing the solution of the equations, it is found that all terms have the same variable XnX_nXn, so the constructor


X x = X n + f ( x ) X_x=X_n+f(x)

namely


f ( x ) = ∑ i = x n – 1 A i    – ( n – x ) a v e f(x)=\sum_{i=x}^{n-1}A_i \; -(n-x)ave

so


∑ i = 1 n ∣ X i ∣ = ∣ X n + f ( 1 ) ∣ + … + ∣ X n + f ( n ) ∣ = ∑ i = 1 n ∣ X n + f ( i ) ∣ \sum_{i=1}^{n}|X_i|=|X_n+f(1)|+\cdots+|X_n+f(n)|=\sum_{i=1}^{n}|X_n+f(i)|

But ∑ I = 1 n ∣ Xn + f (I) ∣ \ sum_ {I = 1} ^ {n} | X_n + f (I) | ∑ I = 1 n ∣ Xn + f (I) ∣ can be viewed as the points on the number axis XnX_nXn point-to-point – f (I), I ∈ [1, n) – f (I), I \ [1, n] – in f (I), I ∈ [1, n) Sum of distances of

So XnX_nXn should take the middle point (high school conclusion, function graph is pan (NNN is even) or pointed bottom pan (NNN is odd))

So as long as we find – f (I), I ∈ [1, n) – f (I), I \ [1, n] – in f (I), I ∈ median [1, n), Can be assigned to him XnX_nXn its generation into the ∑ I = 1 n ∣ Xn + f (I) ∣ \ sum_ {I = 1} ^ {n} | X_n + f (I) | ∑ I = 1 n ∣ Xn + f (I) ∣ is either

PS:PS:PS: F (x) f (x) f (x) has a recursive method of f (I) = f (I + 1) + Ai – avef (I) = f (I + 1) + A_i avef (I) = f (I + 1) + Ai – ave, from backward circulation, Don’t use f (x) = ∑ I = xn – 1 ai – n – (x) avef (x) = \ sum_} {I = x ^ {}, n – 1 A_i \; -(n-x) AVef (x)=∑ I = Xn −1Ai−(n−x) AVE, which causes TLETLETLE

ACACAC code

R73269788 Record details

Programming language C++20 code length 494B time 2.34s memory 8.05MBCopy the code
#include<bits/stdc++.h>
#defineFOR(i,a,b) for(int i=(a); i<=(b); ++i)
#defineROF(i,a,b) for(int i=(a); i>=(b); --i)
#define ll long long
using namespace std;

const int N = 1e6+1;
int n,a[N],f[N];
ll ave=0,ans=0,Xn;

int main(a){
    cin>>n;
    FOR(i,1,n){
        cin>>a[i];
        ave+=a[i];
    }
    ave/=n;// It must be divisible
    f[n]=0;
    ROF(i,n- 1.1)
        f[i]=f[i+1]+a[i]-ave;
    sort(f+1,f+n+1);
    Xn=-f[(n+1) /2];
    FOR(i,1,n)
        ans+=abs(Xn+f[i]);
    cout<<ans;
    return 0;
}
Copy the code