给定一个整数数组，找出使每个值相等的最小步骤数。

Question

给定一个整数数组，找出使每个值相等的最小步骤数。

algorithmsortingdiscrete-mathematics

7

我在练习算法时遇到了这个问题。我无法解决它。我阅读了提供的题解，但它并没有解释解决方案背后的概念或想法。这是问题链接（Question）。

问题陈述---> 有N个男孩坐在圆圈里。每个男孩手上都有一些苹果。你发现总苹果数可以被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;
}

我正在寻找关于上述代码/逻辑的解释。它是如何给出最少步骤的？欢迎任何其他解决方案/方法（不一定是代码），但请解释您的方法。如果有任何不清楚的地方，请访问链接或在评论部分提问。

- Divyanshu

这段代码对你来说是否给出了正确的答案？ - fafl

是的，这是问题设定者提供的官方实现（解决方案），并非我自己的。 - Divyanshu

2个回答

1

这是我解释算法正确性的原因：

数组b告诉我们第 i 个男孩应该向右传递多少苹果，以便他拥有平均数量的苹果（这是目标）。如果值为负，则意味着他需要将苹果传递到左边。数组b考虑了前几个男孩传递的苹果。您可以这样想：如果第一个男孩一开始就拥有超过平均数量的苹果，则b [1]告诉我们这个第一个男孩应该向右传递多少苹果。但是，如果他一开始就比平均水平低，则b [1]告诉我们第二个男孩应该向左传递多少苹果。在这种情况下，值将为负数。尽管索引1现在指向不同的人，但实际上并不重要，因为我们只关心要传递的苹果总量。在此之后，只要我们假设男孩们没有毫无理由地来回传递苹果，所有其他值b [i]都会强制执行。

这里有个问题：我们已经看到，如果每个人都传递 b[i] 个苹果，最终每个人都会拥有平均数量的苹果。现在，如果每个人传递 b[i] + x 个苹果，其中 x 是任意数，会怎样呢？我们仍然可以让每个人拥有平均数量的苹果！为什么呢？因为在这种情况下，一个人向右传递了 x 个苹果，但是他从左边的人那里得到了 x 个苹果，所以最终他拥有的苹果数量与每个人传递 i 个苹果时一样多。如果每个人传递 b[i] 个苹果，传递的总苹果数量将是 abs(b[0]) + abs(b[1]) + … + abs(b[n-1])。然而，我们知道，让男孩们每个人传递 b[i] + x 个苹果也可以达到目标。我们的目标是尽量减少传递的苹果总数。换句话说，我们的目标是尽量减小表达式 abs(b[0] - x) + abs(b[1] - x) + … + abs(b[n-1] - x) 的值。因此，我们必须找到一个值 x，使得这个总和最小。事实证明，数字 b[i] 的中位数始终是最优解。为什么呢？现在考虑选择一个大于中位数的数字。在这种情况下，我们可以通过让 x 稍微减小来使总和更小，因为当前数字左边的数字比右边的数字多，因为我们在中位数的右侧。这是由中位数的定义所决定的。如果我们选择比中位数小的数字，情况也是对称的。因此，中位数本身将始终是最优解。如果数字的数量是偶数，并且有两个中位数，则它们都是同样优秀的，任何介于它们之间的数字也是一样的。

请注意一件事情：我们在开始时给b[0]赋值的值实际上并不重要！你可以在代码中更改那行为 b[0] = 2356235; 或者任何你喜欢的值，你会发现程序仍然能正常工作。所有其他值将基于此值确定。你可以这样想，第一个人传递多少个苹果并不重要，只要其他人按照规则行动即可。通过选择b[0]=0，我们找到了一种平均分配苹果的方法。然而，这种方式并不一定是最优的。这就是为什么我们使用中位数技巧来找到最优解的原因。希望这有所帮助。

- tykkipeli

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tezra · Accepted Answer

这里是一份注释过的代码，应该会有所帮助。但基本上，这个算法的想法是：由于每次只能移动一个苹果一个空格，所以需要移动的苹果数加上每个苹果需要移动的步数就是需要的步数。这是为什么好的注释/变量名很重要的例子，特别是在使用这样复杂的算法时。

#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;
}

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