给定一个整数数组,找到使每个值相等的最小步数

Question

我正在练习算法,并遇到了这个问题.我无法解决它.我阅读了所提供的社论,但它没有解释解决方案背后的概念或想法.这是问题链接(问题).

问题陈述 - >

N个男孩坐在一个圆圈里.他们每个人手里都有一些苹果.你会发现苹果的总数可以通过划分ñ.所以你想要在所有男孩中平分苹果.但他们是如此懒惰,以至于他们每个人都只想一步给一个邻居一个苹果.计算使每个男孩拥有相同数量苹果的最小步数.

输入 - > 输入的第一行是整数N,第二行包含N个数字,表示第i个男孩的苹果数.

输出 - >使每个男孩拥有相同数量的苹果的最小步数.

这是官方实施:

#include<bits/stdc++.h>
#define mod 10001
using namespace std;
typedef long long LL;
int main()
{
    int n,a[10000],avg;
    LL b[mod],val=0,s=0,m;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s+=a[i];
    }
    avg=s/n;
    b[0]=0;
    for(int i = 0; i < n-1; i++){
        b[i+1] = b[i]+a[i]-avg;
    }
    sort(b,b+n);
    m = -b[n/2];
    for(int i=0;i<n;i++)
    {
        val += abs(b[i]+m);
    }
    cout<<val;
    return 0;
}

我正在寻找上述代码/逻辑的解释.它是如何给出最少的步骤？我们欢迎任何替代解决方案/方法(不一定代码),但请解释您的方法.

如果有任何不清楚的地方,请访问链接或在评论部分询问.

Answer 1

这是代码的注释版本，应该会有所帮助，但基本上，其想法是，由于每一步只有一个苹果可以移动一个空间，因此所需的步数是需要移动的苹果数 + 步数每个苹果都需要移动。这是为什么好的注释/变量名称很重要的一个例子，特别是在使用像这样的复杂算法时。

#include<bits/stdc++.h>
#define mod 10001
using namespace std;
typedef long long LL;
int main()
{
    int n,apples[10000],avg;
    LL b[mod],val=0,sum=0,median;

    // Read number of boys
    cin>>n;

    for(int i=0;i<n;i++)
    {
        // Read i'th boy's # of apples
        cin>>apples[i];
        // And add to sum while while we are at it.
        sum+=apples[i];
    }

    // Get average (desired apples per boy)
    avg=sum/n;
    // Clear value of first index
    b[0]=0;
    // Assuming only passing right, 
    // How many apples does boy[i] need to pass right? 
    // (Negative value means needs to pass left.)
    for(int i = 0; i < n-1; i++){
        // Apples this boy needs + needs to pass along
        b[i+1] = b[i]+apples[i]-avg;
    }

    // Sort passes
    sort(b,b+n);
    // Take median, save as negative number
    median = -b[n/2];
    // Sum deference of all passes from the median. 
    // (negate steps where both boys needs are met by same pass)
    for(int i=0;i<n;i++)
    {
        val += abs(b[i]+median);
    }

    cout<<val;
    return 0;
}

这就是代码正在做的事情，但是其他人需要在另一个答案中添加正确性证明。