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

EN

设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元素是使用该字符串的位置。因此，这个全局最小值总是适合我们的目的。