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

题目来源: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

上一篇:2021牛客寒假算法基础集训营3 A模数的世界


下一篇:平方和与立方和