algorithm - CodeJam 2011 : Solution for Gorosort?

Question

问题可以在这里找到:
http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

我不明白为什么
答案 = 否。不在正确位置的元素

例如，假设我必须对这个数组进行排序:

3 1 2

所以我是这样认为的:

Array: 3 1 2  1st: freeze 2 to sort 1 (take 2 hits)  Array: 1 3 2  2nd: freeze 1 to sort 2 and 3 (take another 2 hits)

因此，我的答案是4，但正确答案是3。
谁能给我解释一下这个问题？

Answer 1

他们解释的解决方案是始终只保留正确排序的项目。如果您对三个未排序的元素执行此操作，那么在第一次尝试后，您有 1/6 的机会对所有元素进行排序(即我们在一次点击后完成)，有 3/6 的机会对其中一个项目进行排序(并且您平均需要 2 次以上的命中)和 2/6 的机会没有被排序(并且你仍然需要与开始时相同的 hist 计数)。这为您提供了一个简单的循环公式，在评估后得出，平均而言，您需要 3 次命中才能对 3 个未排序的项目进行排序。

您的策略给出错误结果这一事实仅意味着它不是最佳策略。

虽然他们的解决方案并不是唯一提供相同结果的解决方案，但只是最简单的。另一种可能的方法是保存所有已排序的项目(如果有的话)，加上一些未排序的。但是条件是你没有持有的所有元素都必须能够在你不松开你持有的元素的情况下到达正确的位置(或者换句话说，它们必须在排列中形成 cycle(s) ).

考虑以下示例:

1 3 2 5 6 4

有 5 个未排序的项目，因此 Google 的解决方案平均需要 5 次匹配。

1 已排序，因此我们必须保留它。如果我们也持有 5、6 和 4，则剩余的项(3 和 2) 可以到达正确的位置。当我们这样做时，他们平均会在 2 次点击中到达那里。现在我们有 3 个未排序的项目，我们平均可以在 3 次点击中对它们进行排序。 (我们必须让它们全部自由，因为它们形成一个循环。)所以这种方法虽然更复杂，但与原来的方法一样快。