关于 糖果传递 一题的思路+代码

题目来源：AcWing 122.糖果传递

题目描述

有n个小朋友坐成一圈，每人有a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为1。
求使所有人获得均等糖果的最小代价。

输入描述

第一行输入一个正整数n，表示小朋友的个数。
接下来n行，每行一个整数a[i]，表示第i个小朋友初始得到的糖果的颗数。

输出描述

输出一个整数，表示最小代价。

数据范围

1 ≤ n ≤ 1000000,
0 ≤ a[ i ] ≤ 2×109,
数据保证一定有解。

输入样例

4
1
2
5
4

输出样例

4

OP

这道题代码不难，主要是思路，通过数学方法转化问题。

思路

我们假设第 i 名小朋友有 a[ i ] 颗糖，并向其右侧小朋友传递 x[ i ] 颗糖（ x[ i ] 为整数，若为负值即说明反向传递）。（ x[ n ] 也可以视作 x[ 0 ] ）

在这种假设下，我们的所求即为 $| x[ 1 ] | + | x[ 2 ] | + ... + | x[ n - 1 ] | + | x[ n ] |$ 的最小值。

设传递之后，每名小朋友均有 p 颗糖，我们可以列出如下方程组：

$a[ 1 ] - x[ 1 ] + x[ n ] = b$
$a[ 2 ] - x[ 2 ] + x[ 1 ] = b$
…
$a[ n - 1 ] - x[ n - 1 ] + x[ n ] = b$
$a[ n ] - x[ n ] + x[ n - 1 ] = b$

整理①式，我们可以得出：$x[ 1 ] = x[ n ] - b + a[ 1 ]$
将其代入②式，便可以得出$x[ 2 ] = x[ n ] - 2 * b + a[ 1 ] + a[ 2 ]$
以此类推：$x[ i ] = x[ n ] - i * b + a[ 1 ] + a[ 2 ] + ... + a[ i ]$

此时，我们所求即转化为
$| x[ n ] - b + a[ 1 ] | + | x[ n ] - 2 * b + a[ 1 ] + a[ 2 ] | + ... + | x[ n - 1 ] = x[ n ] - ( n - 1 ) * b + a[ 1 ] + a[ 2 ] + ... + a[ n - 1 ] | + | x[ n ] = x[ n ] - 0 * b + a[ 1 ] + a[ 2 ] + ... + a[ n ] |$
的最小值。

现在，我们就可以将上式看作另一个问题：
数轴上有一系列点： $b + a[ 1 ] , 2 * b + a[ 1 ] + a[ 2 ] , ( n - 1 ) * b + a[ 1 ] + a[ 2 ] + ... + a[ n - 1 ] , 0 * b + a[ 1 ] + a[ 2 ] + ... + a[ n ]$ ，求某一点（x[ 0 ]）与他们所有点的距离之和最短。

将 x[ 0 ] 放在这一系列点的中位数处显然是最短的，就如货仓选址这道题。

代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    static long long n,a[1000006]={0},d[1000006],i,p;
    cin>>n;
    for(i=1;i<=n;i++){scanf("%lld",&a[i]);d[i]=a[i]+d[i-1];}
    p=d[n]/n;
    for(i=1;i<=n;i++)
    {
        d[i]-=i*p;
    }
    sort(d+1,d+1+n);
    long long sum=0;
    for(i=1;i<=n;i++)
    {sum+=abs(d[i]-d[(n+1)/2]);}//与中位数距离
    printf("%lld",sum);
    return 0;
}

ED

y总yyds