糖果传递

题目链接

分析过程

1->2->3->4->...->n->1  构成一个环
x1 x2 x3 x4 .... xn   xi表示xi给xi+1糖果的个数，xi可正可负可为零。
本题要求|x1|+|x2|+|x3|+.....+|xn|的最小值。
 
限制条件：最后每个人获得均等糖果。
av表示平均值，a数组表示每个人初始糖果的数量。

a[1] - x1 + xn = av;                    a[1] - x1 + xn = av;
a[2] - x2 + x1 = av;                    a[2] - x2 + x1 = av;
a[3] - x3 + x2 = av;                    a[2] + a[3] - x3 + x1 = 2 * av;
a[4] - x4 + x3 = av;                                     .                                                          
        .                  ==========>                   .                                                               等价成cn。  cn = cn-1 + an - av; (n >= 2)
        .                                                .                                                                 ^         c1 = 0;
        .                                                .                                                                 |
        .                                                .                                  通项公式              ----------------------
a[n-1] - xn-1 + xn-2 = av;              a[2] + ... + a[n - 1] - xn-1 + x1 = (n - 2) * av;                       | n                    |
a[n] - xn + xn-1 = av;                  a[2] + ... + a[n] - xn + x1 = (n - 1) * av;        =========>  xn = x1 +| ∑ an - (n - 1) * av; | (n >= 2)                     
                                                                                                                |n=2                   |
                                                                                                                 ----------------------
经过上面的等价推导，所以：
   |x1|+|x2|+|x3|+.....+|xn| ==> |x1 + c1|+|x1 + c2|+|x1 + c3|+.....+|xn + cn|
   到这里就转换成AcWing 104.货仓选址这道题了。(链接在下方)
                                                                                                           

AcWing 104.货仓选址 ### 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
LL a[N], c[N];
LL sum, ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    
    LL avg = sum / n;  // 因为题目保证有解，因此平均数必为整数。
    
    c[1] = 0;
    for (int i = 2; i <= n; i++)
        c[i] = c[i - 1] + a[i] - avg;
    
    sort(c + 1, c + 1 + n);
    
    int mid = c[(1 + n) / 2];
    for (int i = 1; i <= n; i++)
        ans += (LL)abs(mid - c[i]);
        
    cout << ans << endl;
    
    return 0;
}