让一群人坐在一起需要最小的跳跃 - 贪婪的方法证明？

发布于 2025-02-07 14:32:24 字数 997 浏览 1 评论 0 原文

我发现了一种贪婪的算法问题，我们必须找到最小的算法。让人们坐在一起需要的跳跃。
这是链接与文章供参考。

文章中的问题描述：

标题：
让一群人坐在一起需要的最小跳跃。
描述：
给定长度为n的字符串n由“ x”和“。”组成。给定的字符串表示“ x”和“”的一排座位。分别代表被占领和空无一人的座位。任务是最大程度地减少啤酒花或跳跃的总数，以使所有乘员坐在一起，即彼此之间，没有它们之间的空缺座位。
示例：
- 输入：s =“。。。。 x。。 xx。。。 x。。”
  输出：5
  说明：让第五座位的人跳到第七座位2位。使第13个座位的人跳3个位置到第10个席位。因此，所需的跳跃总数= 2 + 3 = 5。
- 输入：s =“ xxx。。。。。。。。 xxxxxx”
  输出：24
  说明：将乘员从第一，第二和第三位置移至第9、10、11位。因此，所需的跳跃总数=（11 - 3） +（10 - 2） +（9 - 3）= 24。
方法：
这个想法是使用贪婪的方法来解决这个问题。观察到，将元素转移到所有在场人员中的人或中心人之间的中位数元素总是最佳的。当我们转移到中间位置时，跳跃的数量始终将是最小的。

贪婪的解决方案说，将元素转移到中位数。但是找不到证据。是否存在使用这种方法的数学证明？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

迷迭香的记忆 2025-02-14 14:32:24

令 a [i] 为人的初始位置 i （基于0的索引），其中人的顺序设置为增加位置的顺序，> n 是人的数量。假设所有人连续坐着的位置的最终间隔从位置 t 开始。由于人们的相对顺序没有改变，因此我们看到该人 i 从 a [i] 移动到 t + i 。何时以及如何确切地发生这一举动对我们来说并不重要，但是一个人无需朝着远离目标位置的方向跳下来，因此它贡献了 | a [i] - （t + i）| == | t - （a [i] - i）| == | t -b [i] | 跳跃，其中 b ，由 b [i] = a [i] - i 定义em> non -decreasing 数组，因为 a 是严格增加（因此 b [i + 1] -b [i] == a [i [i] + 1] - （a [i] + 1）＆gt; = 0 ）。

因此，从位置开始 t IS total [t] = sum（i，| t -b [i] |）的最小值是 t 是 t 。现在， d_total [t] = total [t + 1] - 总计[t] （i，t＆gt; = b [i]？1：-1）== count（i，t＆gt; = b [i]） - count（i，t＆lt; b [i]）== 2*count （i，t＆gt; = b [i]） - n 是 total 的'离散导数'，很容易看到随着 t 的增加，， d_total [t] 是非折扣的，在某些 i 的点上增加了 t == b [i] 2 *计数（i，t == b [i]）。 的最小值发生在最小的 t 中， d_total [t] 是正（意味着 count> count（i，t）＆gt; = b [i]）＆gt; n/2 ）。

特别是，对于奇数 n == 2*k + 1 这样的 t 正是 b 的中值，而所得间隔的“中心” IS t + k == b [k] + k == a [k] ，即 a 的中位数，如解决方案中所假设。对于 n == 2*k 我们在 t b [k -1] 和 b [k] 其中 total [t] 是最小的（ d_total [t] == 0 for tє[b [k [k [k] -1]; b [k] -1] t == b [k] 是最小的 d_total [t]＆gt;这意味着所产生的间隔的“左中心”是 t + k -1є[a [k -1]; a [k] -1] （或等效地，'右中心' t + kє[a [k -1] + 1; a [k]] ），所以我们在这种情况下，如果 a [k]＆gt; A [K -1] 。

在任何情况下，正如我们看到的，最佳策略是向中位数跳跃（或 n 案例中的“中间间隔”，但随后将中位数定义为此间隔的末端的平均值，我们，我们仍然可以说“朝向中间人”的职位。

最后，也许这很明显，但是对于完整性：请注意，获得的全局最小 t 不会产生超出输入字符串的间隔，因为在两个奇偶校验中，很容易证明， a [0]＆lt; = t＆lt; = t + n -1＆lt; = a [n -1] 和 a 元素是该字符串的位置。因此，这种全球最低限度始终适合我们的目的。

Let a[i] be initial position of person i (0-based indexing), where order of people is set to be in order of increasing positions, and n be the count of people. Suppose that final interval of positions, where all people sit consecutively, starts at position t. Since relative order of people doesn't change, we see that person i moves from a[i] to t + i. When and how exactly this move happens is unimportant to us, but there's never need for a person to jump in the direction away from its target position, so it contributes |a[i] - (t + i)| == |t - (a[i] - i)| == |t - b[i]| jumps, where b, defined by b[i] = a[i] - i, is a non-decreasing array since a is strictly increasing (thus b[i + 1] - b[i] == a[i + 1] - (a[i] + 1) >= 0).

So, minimal total number of jumps for resulting interval starting at position t is total[t] = sum(i, |t - b[i]|). Now, 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 is the 'discrete derivative' of total, and it's easy to see that as t increases, d_total[t] is non-decreasing, increasing at points where t == b[i] for some i by 2*count(i, t == b[i]). The smallest value of total happens at the smallest t for which d_total[t] is positive (which means count(i, t >= b[i]) > n/2).

In particular, for odd n == 2*k + 1 such t is exactly the median of b, and 'center' of resulting interval is t + k == b[k] + k == a[k], i.e. median of a, as is assumed in the solution. For even n == 2*k we have inclusive interval of t between b[k - 1] and b[k] where total[t] is minimal (d_total[t] == 0 for t є [b[k - 1]; b[k] - 1] and t == b[k] is the smallest where d_total[t] > 0), which means that resulting interval's 'left center' is t + k - 1 є [a[k - 1]; a[k] - 1] (or, equivalently, 'right center' t + k є [a[k - 1] + 1; a[k]]), so we have several optimal solutions in this case if a[k] > a[k - 1].

In any case, as we see, optimal strategy is to jump towards the median (or 'median interval' in even n case, but since median is then defined as average of the ends of this interval, we still can say 'towards the median') of the starting people positions.

Finally, maybe this is obvious, but for completeness: note that the obtained global minimum t doesn't produce interval that goes beyond the input string because, as is easy to prove in both parity cases, a[0] <= t <= t + n - 1 <= a[n - 1], and a elements are positions withing this string. So, this global minimum is always suitable for our purposes.