Table of contents: Algorithm Diary

122. Candy transfer – AcWing

Topic describes

There are NNN children sitting in a circle, each has a[I]a[I]a[I]a[I]a[I] candy.

Each person can only pass candy to the right or left two people.

Each candy pass costs 111.

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

Input format

On the first line, enter a positive integer NNN to indicate the number of children.

Next NNN line, each line is an integer a[I]a[I]a[I]a[I], which represents the number of sweets that the third child gets initially.

The output format

Output an integer representing the minimum cost.

Data range

1≤n≤ 1000000,0 ≤a[I]≤2×1091≤n≤ 1000000,0 ≤a[I]≤2×10^91≤n≤ 1000000,0 ≤a[I]≤2×109 data must have solutions.

Enter the sample

4, 1, 2, 5, 4Copy the code

The output sample

4
Copy the code

Algorithm ideas

For the sake of description, given the range 0≤ I

Xix_ixi is positive when giving candy to another child; Xix_ixi is negative when receiving candy from another child. Because they tell us that the cost of passing one candy per person is 111, xix_ixi is always positive as the cost of passing candy. Res =∣x0∣+∣x1∣+… + ∣ xn – 1 ∣ res = | x_0 | | + x_1 | +… + | x_ {n – 1} | res = ∣ x0 ∣ + ∣ x1 ∣ +… Plus ∣xn minus one ∣, the problem is going to be minimizing resresres.

The problem is guaranteed to have a solution, so the number of sweets per child ends up with: Average = Average = Average = the total number of sweets per child.

For the thousandth child, he gave the n−1n-1n−1 child x0x_0x0 sweets, and the 111th child gave him x1x_1x1 sweets, so, Average = A0 − X0 + x1Average =a_0-x_0+ X_1Average = A0 − X0 +x1 (①);

For the 111th child, he gave the 000th child x1x_1x1 candy and the 222nd child x2x_2x2 candy, so average= A1 − X1 + x2Average =a_1-x_1+ X_2Average = A1 − X1 +x2 (②);

For the 222nd child, he gave x2x_2x2 candy to the 111st child and x3x_3x3 candy to the 333rd child, so average= A2 − X2 + x_2+ X_3Average = A2 −x2+x3 (③);

And so on.

Observe that the above equation contains NNN variables (x0,x1… Xn – 1 x_0 x_1… x_{n-1}x0,x1… Xn −1), consider reducing the number of variables. Wherein, variable x1x_1x1 can be eliminated by formula ①, variable x2x_2x2 can be eliminated by formula ②, and so on. Therefore, we can try to deduce:


x 0 = x 0 – 0 make c 0 = 0 x 0 = x 0 – c 0 X_0 = x_0-0 \ \ make c_0 = 0 \ \ x_0 = x_0 – c_0

According to formula 1,


x 1 = a v e r a g e – a 0 + x 0 x 1 = a v e r a g e – a 0 + x 0 – c 0 make c 1 = a 0 + c 0 – a v e r a g e x 1 = x 0 – c 1 X_1 = business – a_0 + x_0 \ \ x_1 = business – a_0 + x_0 c_0 \ \ make c_1 = a_0 + c_0 – business \ \ x_1 = x_0 – c_1

According to equation ②,


x 2 = a v e r a g e – a 1 + x 1 x 2 = a v e r a g e – a 1 + x 0 – c 1 make c 2 = a 1 + c 1 – a v e r a g e x 2 = x 0 – c 2 X_2 = business – a_1 + x_1 \ \ x_2 = business – a_1 + x_0 – c_1 \ \ to c_2 + c_1 – business \ \ x_2 = = a_1 x_0 – c_2

According to equation ③,


x 3 = a v e r a g e – a 2 + x 2 x 3 = a v e r a g e – a 2 + x 0 – c 2 make c 3 = a 2 + c 2 – a v e r a g e x 3 = x 0 – c 3 X_3 = business – a_2 + x_2 \ \ x_3 = business – a_2 + x_0 c_2 \ \ make c_3 = a_2 + c_2 – business \ \ x_3 = x_0 – c_3

And so on.

And if you look at that,


x i = x 0 – c i c i = a i – 1 + c i – 1 – a v e r a g e r e s = ∣ x 0 ∣ + ∣ x 1 ∣ + . . . + ∣ x n – 1 ∣ r e s = ∣ x 0 – c 0 ∣ + ∣ x 0 – c 1 ∣ + . . . + ∣ x 0 – c n – 1 ∣ x_i=x_0-c_i\\ c_i=a_{i-1}+c_{i-1}-average\\ res=|x_0|+|x_1|+… +|x_{n-1}|\\ res=|x_0-c_0|+|x_0-c_1|+… +|x_0-c_{n-1}|

∣ x0 – ci ∣ | x_0 – c_i | ∣ x0 – ci ∣ geometric meaning is, the distance from x0x_0x0 to cic_ici. Therefore, the original problem is further transformed into, find from x0x_0x0 to c0,c1… Cn – 1 c_0 c_1… c_{n-1}c0,c1… The minimum distance sum of cn−1.

When x0x_0x0 is set to c0, C1… Cn – 1 c_0 c_1… c_{n-1}c0,c1… If cn−1 is the median, the minimum value resresres exists.

Tips: I noticed
0 Or less a [ i ] Or less 2 x 1 0 9 0 or less a [I] 2 x 10 ^ 9 or less , so the sum has the risk of exploding int, so we need to use long long.

AC code

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6+10;
int n;
int a[N];
int c[N];
int main(a) {
    cin>>n;
    long long sum = 0;
    for(int i = 0; i < n; ++i) {
        cin>>a[i];
        sum += a[i];
    }
    int ave = sum / n;
    c[0] = 0;
    for(int i = 1; i < n; ++i) {
        c[i] = a[i- 1] + c[i- 1] - ave;
    }
    sort(c, c+n);
    long long res = 0;
    int mid = c[n/2];
    for(int i = 0; i < n; ++i) {
        res += abs(c[i] - mid);
    }
    cout<<res<<endl;
    return 0;
}
Copy the code