使一群人坐在一起所需的最小跳跃--证明了贪婪的做法？

Question

我发现了一个贪婪的算法问题，在这里我们必须找到最小的不。使人坐在一起所需的跳跃。

这里是一篇文章的链接，供参考。

文章中的问题说明：

• 标题： 使一群人坐在一起所需的最低限度跳跃。
• 描述： 给定长度为N的字符串S，由‘x’和‘.’组成。给定的字符串表示一排座位，其中“x”和“.”分别代表已占和无人的席位。任务是最大限度地减少跳伞或跳跃的总数，使所有的人坐在一起，也就是说，在彼此之间没有任何空位。
• 示例：

- Input: S = “. . . . x . . x x . . . x . .”

产出:5

说明:让第5位的人跳2位到第7位。让人在第13位跳跃3位到第10位seat.Therefore，总跳跃次数=2+3= 5。

- Input: S = “x x x . . . . . . . . x x x x x x”

产出: 24

说明:将乘员从第一、第二和第三位置分别移至第九、第十、第十一位置。因此，所需跳转总数=(11-3)+(10-2)+(9-3)= 24。

• 方法： 这个想法是用贪婪的方法来解决这个问题。注意，在所有在场人员中，将元素转移到中间元素或中间元素总是最优的。当我们将点移到中位数时，跳转的次数总是最小的。

贪婪的解决方案是将元素转移到中间值。但还没有找到任何证据。是否存在使用这种方法的数学证明？

Answer 1

设a[i]是person i (基于0的索引)的初始位置，其中人员的顺序设置为增加位置的顺序，而n是人数的计数。假设最后的位置间隔，所有的人都连续地坐着，从t位置开始。由于人的相对顺序没有变化，我们看到person i从a[i]移动到t + i。何时以及如何发生这一移动对我们来说并不重要，但是从来不需要一个人跳到远离其目标位置的方向，因此它贡献了|a[i] - (t + i)| == |t - (a[i] - i)| == |t - b[i]|跳转，其中由b[i] = a[i] - i定义的b是一个不递减的数组，因为a严格地增加(因此b[i + 1] - b[i] == a[i + 1] - (a[i] + 1) >= 0)。

因此，从位置t开始的结果间隔的最小跳转总数是total[t] = sum(i, |t - b[i]|)。现在，d_total[t] = total[t + 1] - total[t] == sum(i, |t - b[i] + 1| - |t - b[i]|) == sum(i, t >= b[i] ? 1 : -1) == count(i, t >= b[i]) - count(i, t < b[i]) == 2*count(i, t >= b[i]) - n是total的‘离散导数’，可以很容易地看到，随着t的增加，d_total[t]是不递减的，在由2*count(i, t == b[i])对某些i的t == b[i]点处增加。total的最小值发生在d_total[t]为正的最小t (意为count(i, t >= b[i]) > n/2)。

特别地，对于奇数n == 2*k + 1，这样的t正好是b的中值，结果区间的“中心”是t + k == b[k] + k == a[k]，也就是a的中值，正如在解中所假定的。即使是n == 2*k，在b[k - 1]和b[k]之间也有包含t的区间，其中total[t]最小( t є [b[k - 1]; b[k] - 1]和t == b[k]的d_total[t] == 0是最小的d_total[t] > 0)，这意味着得到的区间‘左中心’是t + k - 1 є [a[k - 1]; a[k] - 1] (或者，等效地说，‘右中心’<代码>d40)，所以在这种情况下，如果a[k] > a[k - 1]，我们有几个最优的解决方案。

在任何情况下，正如我们所看到的，最优策略是跳向中间值(在偶数n情况下是“中间间隔”)，但是由于中位数被定义为这个区间结束的平均值，我们仍然可以说是“朝向中间值”的起始位置。

最后，这可能是显而易见的，但为了完整性:请注意，获得的全局最小t不会产生超出输入字符串的间隔，因为在这两种奇偶校验情况下都很容易证明，a[0] <= t <= t + n - 1 <= a[n - 1]和a元素是使用该字符串的位置。因此，这个全局最小值总是适合我们的目的。