【题解】糖果传递

关于本题

1. 本题前身：仓库选址 。

2. 如何将该题转化到仓库选址是难点。首先设未知数 x[i] 表示第 i 名小朋友分出的糖果数（x 可以为负数）。根据糖果的分出的方向建立一个单向无环链表。可以证明是一定无环的，因为如果有环说明一定可以让每个小朋友都少分出一部分糖果使得环消失。但是为了便于计算我们可以补上一条为零的边，使得整个链表形成一个环。

3. 根据图示可以发现我们的目标是使得
   $$
   \sum_{i=1}^n |x_i|
   $$
   值最小。

4. 通过推导公式可以发现第三步的求值方式与 仓库选址 相同。

图解

贪心 C++ 2306ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1000010, M = N * 2;

int n;
int a[N];
// c[i] = avg - ∑(a1~ai) 
LL c[N];

int main()
{
    cin >> n;

    LL sum = 0;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }

    LL avg = sum / n;
    for (int i = 1; i < n; i ++ )
    {
        c[i] = c[i - 1] + (avg - a[i]);
    }

    // c[n] = 0;
    sort(c + 1, c + n + 1);
    int x = n + 1 >> 1;
    sum = 0;
    for (int i = 1; i <= n; i ++ ) sum += abs(c[i] - c[x]);

    cout << sum;
    return 0;
}