洛谷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