2

问题：我们有一个大小数组，n我们最多可以执行K每个操作可以执行的操作

  1. 将反转次数减少 1。
  2. 对整个数组进行随机洗牌。

我的问题是以K这样一种方式执行操作，以使最终数组中的预期反转次数最小化。

约束：
100 个测试用例，
1 < n < 100
1 < K < n(n-1)/2

我的方法：我正在考虑动态编程解决方案。我可以使用马洪数计算e在大小数组中精确反转的概率。我还逐行n填充数组，表示在执行操作后数组中具有反转的最小预期反转，然后使用它我可以为数组中所有可能的反转生成最小预期值。dp[k+1][1+n(n-1)/2]dp[i][j]ji(i+1)<sup>th</sup>

由于 c++ 中双精度数的限制，这种方法的问题是概率不准确，并且该算法O(kn<sup>2</sup>)适用于每个非常慢的测试用例。

例如：在大小为 100 = ~
的数组中没有反转的概率（我认为这里缺乏精度）。1.0/factorial(100)10<sup>-160</sup>

我认为有一些准确和更有效的方法。请提出一些想法。

谢谢

4

1 回答 1

1

为了回答您的问题，您将需要能够计算预期的#inversions，假设您有 k 个左移并假设在第 k 个移动时您洗牌，然后您决定停止洗牌（然后只需减去 1）或继续洗牌取决于你洗牌后得到多少反转。如果您只剩下两步并且当前的#inversions 大于n(n-1)/4，这很容易。基本上你先洗牌，然后停止洗牌，如果在你第一次洗牌后反转次数为 n(n-1)/4 或更低，则停止洗牌并为你的第二步减去 1，如果反转次数大于 n，你再次洗牌(n-1)/4 在你第一次洗牌后。但是，对于超过 2 个动作，事情变得更加复杂，因为在第 k 次移动时，如果你洗牌，你可以选择反转次数 Nk 的上限 Nk，你将停止，然后减去 1，你需要优化这个 Nk，以便预期的反转次数总体上是最小的。显然，如果 k 较大，则应选择较小的 Nk，但问题是多少。如果您可以计算 Nk（对于每个 k），那么您将解决您的问题。

我的直觉是，您可以使用某种递归公式在基本上 O(nK) 时间内为所有 k=1,2,...,K 求解 Nk。如果我弄清楚细节，我会更新。如果为真，则意味着您也可以在基本上 O(nK) 时间内求解预期的反转次数。

于 2014-09-09T18:54:12.800 回答