洛谷P2512 [HAOI2008]糖果传递 题解

题目链接：P2512 [HAOI2008]糖果传递

题意：

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。

输入格式：

小朋友个数 $n$，下面 $n$ 行 $a_i$。

输出格式：

求使所有人获得均等糖果的最小代价。

数据范围：

对于 $100\%$ 的数据 $n\le 10^6$。

设最后每个人的糖果为 $\bar{a} = \frac{1}{n} \sum_{1 \le i \le n} a_i$ ，记 $b_i = a_i -\bar{a}$

则题目变为如何将 $b_i$ 全部转化为 $0$ 。

设 $x_i$ 表示最终方案中 $i$ 给 $i+1$ 了多少糖果（如果 $x_i$ 为负，则代表 $i+1$ 给了 $i$ 多少）

由 $b_i=0$ 得

$$a_i+x_{i-1}+x_i = 0$$

则答案为 $\sum_{i=1}^{n} |x_i|$ ，考虑最小化它。

注意到这里一共有 $n$ 个方程，而独立的仅有 $n-1$ 个

也就是说，任意 $n-1$ 个方程都可以推出剩下那个

于是设 $t=x_1$ ，则

$$\begin{aligned} x_2 &= a_2 + x_1 = a_2 + t \\x_3 &= a_3 + x_2 =a_3 + a_2 + t \\&\cdots \\x_n &= a_n + x_{n-1} = a_n + \cdots + a_2 + t \end{aligned}$$

记 $S_i = \sum_{k=2}^{i} a_k$ ，问题转化为最小化

$$\sum_{i=1}^{n} |s_i + t|$$

记 $x=-t$ ，则问题转化为

在数轴上找一已知点 $x$ 使其与 $n$ 个已知点距离之和最小，显然取中位数位置的那个点。

时间复杂度 $O(n)$ ，用nth_element()来找中位数。

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e6+15))

int n,s,p,a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i], s+=a[i]; s/=n;
    for(int i=1; i<=n; i++) a[i] = a[i] + a[i-1] - s;
    nth_element(a+1,a+(p = (n+1)>>1),a+1+n); s=0;
    for(int i=1; i<=n; i++) s+=abs(a[i]-a[p]);
    cout << s << '\n';
    return 0;
}

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/lydsy1045%3Blg1368%3Blg2512.html