以最少的步数交换盒子

Question

这是一个关于编程竞赛的问题（已经结束了）。我一直在努力解决这个问题，但是没能找到有效的方法。

问题陈述如下：IIIT Allahabad正在庆祝其年度Techno-Cultural Fiesta Effervescence MM12活动，从10月1日至5日。主厨同意为这个节日季节提供糖果。厨师准备了N个装有糖果的盒子，编号为1到N（每个数字恰好出现一次）。厨师非常注重盒子的排列顺序。他想要按照特定的顺序排列盒子，但不幸的是厨师很忙。他要求你帮他重新排列盒子。给定当前盒子的顺序，您必须按指定顺序重新排列盒子。但是有一个限制。您只能交换相邻的两个盒子来达到所需的顺序。输出所需相邻交换的最小次数。

输入

输入的第一行包含一个整数T，表示测试用例的数量。每个测试用例都包含3行，第一行包含一个整数N，表示盒子的数量。接下来的2行每行包含N个数字，第一行是给定的盒子顺序，第二行是所需的顺序。

输出

对于每个测试用例，输出一个整数'K'，表示所需相邻交换的最小次数。限制：

1<=T<=10
1<=N<=10^5

Example 输入：

4

3
1 2 3
3 1 2

3
1 2 3
3 2 1

5
3 4 5 2 1  
4 1 5 2 3  

4
1 2 3 4
2 3 4 1

输出：

2
3
6
3

我对这个问题几乎一无所知。能否有人解释一下这个问题的逻辑呢！

- Akashdeep Saluja

---

@MattPhillips：重点不在于交换数字，而在于计算交换次数，这可能并不涉及交换。 - nhahtdh

6个赞，2个收藏，5个人已经发布了答案，其中许多答案已经得到了赞同，其中一个答案已经被采纳...然而显然“很难确定这里在问什么”，因此这个问题已经被关闭。又是一次SO勇敢的官僚主义者的胜利！ - j_random_hacker

@j_random_hacker：虽然应该将其标记为重复，但我后来发现了一个重复的问题，它描述了与我的帖子相同的方法（二进制索引树/芬威克树）。 - nhahtdh

@j_random_hacker：这是一个好的问题https://dev59.com/vmgu5IYBdhLWcg3wMkbF，另一个不太好但也给了提示https://dev59.com/plHTa4cB1Zd3GeqPWPz9 - nhahtdh

@nhahtdh：嗯。这些问题肯定有着相同的答案，但我不会说它们是同一个问题，因为需要一些逻辑来弄清楚这个问题可以转化成它们。 - j_random_hacker

Answer 1

该问题是一个很经典的竞赛编程问题，需要计算数组中的逆序对。逆序对被定义为一对(i, j)，其中i < j且A[i] > A[j]。

最普遍的版本，给定任意数字的数组并要求计算逆序对的数量，可以通过修改归并排序算法来实现O(n log n)的解决方案。

更受限制的版本中，数组中的最大值有一个合理的上界（注意这不是数组的长度），可以在O(n log m)时间内解决，其中m是数组中的最大值。这里的主要重点是你需要编写的代码量比归并排序方法少得多。

问题是关于计算将数组排序到特定顺序所需的交换次数，可以重构为计算将数组按升序排序所需的交换次数，并归结为计算逆序对的数量。为什么是逆序对的数量？因为你只能在交换相邻元素时解决至多一个逆序对。

你需要创建一个数组，描述盒子相对于最终设置的当前位置。然后算法可以开始：

1. 构建一个长度为m（对于问题中的n，m=n）的树状数组（二进制索引树）。

   我们将使用树状数组来帮助我们计算数组中在当前元素之前的大于当前元素的元素数量。我们将保留迄今遇到的数字的频率，并使用树状数组范围求和查询来获取小于当前元素的元素数量（并推导出大于当前元素的元素数量）。

2. 循环遍历数组的n个元素：

   • 使用范围求和查询来计算已记录的小于当前数字的数字数量。
   • 使用上述信息找出大于当前数字的数字数量。将此添加到逆序计数中。请注意不要包括正在考虑的元素。（*）
   • 将元素的值调整为树状数组中的+1。

3. 积累在(*)步骤中的逆序计数。

问题明确表示元素是唯一的，因此上面的算法将起作用。我只是不确定唯一性是否是必要条件，或者算法是否可以修改以适应存在重复元素的情况。

- nhahtdh

---

另外，你没有解释为什么计算逆序对可以解决给定的问题。 - j_random_hacker

除此之外，它看起来是一个非常全面的答案，但我认为“为什么”这个问题至关重要 :) - j_random_hacker

示例代码在此处：http://pastebin.com/3fBa7PT7。该代码不正确，因此我没有将其包含在我的答案中。除非您愿意重构它，请不要编辑以将其放入我的答案中 - 因为答案已经有足够的步骤来重现该代码。 - nhahtdh

@j_random_hacker：请现在检查我的答案（希望我没有漏掉任何东西）。 - nhahtdh

我只是想讨论一下，我们不能从数字唯一且严格从1到N中获得任何好处吗？也就是说，我们不能比O（NlogN）更快地完成它吗？ - Akashdeep Saluja

Answer 2

将源列表缩减为（1，2，...，N）的排列。（通过将目标的逆应用于源）

然后计算逆序对的数量。

即

vector<int> source = ...;
vector<int> target = ...;

vector<int> inv(N)

for (int i = 0; i < N; i++)
   inv[target[i]] = i;

vector<int> perm(N);

for (int i = 0; i < N; i++)
    perm[i] = source[inv[i]];

然后使用标准算法计算perm中的逆序数。

- Andrew Tomazos

---

为什么计算逆序对是有效的？ - j_random_hacker

假设元素不同（在排列中是必然的），那么任何相邻交换都会将逆序对增加一或减少一。因此，最快的路径是始终选择一个将逆序对减少一的交换。这样的交换必定可用，只需遍历列表并交换第一个反转的相邻对即可。如果没有这样的对，则逆序对= 0，完成操作。 - Andrew Tomazos

好的解释，+1。应该放在主帖中！ - j_random_hacker

Answer 3

假设所需排序的顺序是数字的排序顺序，则问题可以简化为查找数组中逆序对的数量。

如果 i < j 且 array[i] > array[j]，则称 (i,j) 是一个逆序对。这是因为每次相邻元素之间的（最优）交换都会将逆序对的数量减少 1。您可以通过一种类似于归并排序的分治算法在 O(n log n) 中找到逆序对的数量。这里有一个很好的解释 带有C代码。

编辑：证明逆序对的数量等于最优交换的数量：

假设 i 是一个 array 中的位置。交换 array[i] 和 array[i+1] 最多可以减少 1 个逆序对。因此，所需的交换次数至少等于逆序对的数量。另一方面，如果 array 没有排序，我们总是可以找到一对 (i, i+1)，使得 array[i] > array[i+1]（即 (i,j) 是一个逆序对），通过交换 array[i] 和 array[i+1] 来将逆序对的数量减少 1。因此，逆序对的数量等于最小交换次数。

- krjampani

---

将目标排列的逆序应用于源排列，请参见我的答案。 - Andrew Tomazos

这是一个不错的开始。我可以看出为什么相邻交换可以将逆序对数量最多减少1（因为唯一一对位置(i, j)的“逆序性”可以通过相邻交换(i'，i'+1)来改变，是一对(i=i'，j=i'+1)，但如何证明这样的移动总是存在呢？ - j_random_hacker

@j_random_hacker每当我们交换相邻的两个数字A[i]和A[i+1]时，必须满足A[i]>A[i+1]，否则这个交换就不是最优的，实际上会增加逆序对的数量。另一方面，如果数组还没有排序，我们总是可以找到两个相邻的数字A[i]和A[i+1]，使得A[i]>A[i+1]。 - krjampani

这样怎么样？如果A没有排序，那么存在一个索引i，使得A[i]>A[i+1]。否则，如果对于每个i，A[i]<=A[i+1]，那么A已经排序。但是，此时（i，i+1）就是一个逆序。 - krjampani

排序 -> 对于所有的i，A[i] < A[i+1] -> 不存在i使得A[i] > A[i+1]。未排序 -> 不是对于所有的i，A[i] < A[i+1] -> 存在i使得A[i] > A[i+1]。 - Andrew Tomazos

Answer 4

问题可以看作是一个逆序对计数问题，具体如下：

由于数字的优先级已给定，即按照我们应该排序的顺序给出。

考虑这些优先级，并将其替换为数字。

e.g:

3 4 5 2 1  
4 1 5 2 3  

在上面的测试用例中，我们可以观察到4被分配了优先级1，1被分配了优先级2，5被分配了优先级3，依此类推。那么为什么不用这些优先级替换原始列表中的数字呢？

也就是说，将原始列表进行转换。

(3 4 5 2 1) to (5 1 3 4 2) 

现在我们的列表已经转换为

5 1 3 4 2

我们只需要按升序对其进行排序。

现在我们只允许相邻交换，即与冒泡排序有些相关。

冒泡排序所需的交换次数等于每个元素右侧小于当前元素的元素数量之和。

例如：在列表中

5 1 3 4 2

5 在其右侧有 4 个比 5 小的元素。

1 在其右侧没有比 1 小的元素。

3 在其右侧有 1 个比 3 小的元素。

4 在其右侧有 1 个比 1 小的元素。

2 在其右侧没有比 2 小的元素。

现在最终答案是 (4+0+1+1+0)=6。

现在可以使用逆序对计数来计算上述过程，该方法在此处讨论 http://www.geeksforgeeks.org/archives/3968。

注意：我获得的答案非常有用，详细描述了整个过程。 谢谢

- Akashdeep Saluja

Answer 5

我无法在数学上证明这一点，但在4/4的测试案例中，通过从最左边（也可以从最右边）开始将盒子移动到正确的位置，并向右移动，您可以获得最小的交换次数。即：

3 4 5 2 1 //First get the 4 in the right place
4 3 5 2 1 //Done.  Now get the 1 in the right place
4 3 5 1 2
4 3 1 5 2
4 1 3 5 2 //Done.  Now the 5
4 1 5 3 2 //Done.  Now the 2
4 1 5 2 3 //All done.

所以这个算法看起来会给你任何给定输入的最小值。一般情况下最坏的情况是一个反转，这将需要N*(N-1)/2次交换（参见例子2）。

- Matt Phillips

---

这将是O(N^2)的最坏情况，这并不是OP所需要的。 - nhahtdh

是的，但O(N^2)超出了时间限制。 - Akashdeep Saluja

@nhahtdh 不管 OP “需要”什么，解决方案都受问题结构的制约。如果你能在 O(n log(n)) 中完成反转操作（请参见上面及我对顶部帖子的评论），那就让我们看看，并可能推迟对其进行投票，直到实际实现为止。 - Matt Phillips

@AkashdeepSaluja 时间限制是如何确定的？比赛组织者告诉你这个了吗？ - Matt Phillips

我忘记输入了，但只有2秒钟。 - Akashdeep Saluja

@MattPhillips：你可以看一下修改后的归并排序算法，或者尝试模拟我的算法。在我的算法中，反转可以使用Fenwick树（rsq和adjust总是log m）以O(n log m)（其中m = n）完成。竞赛问题通常需要1-3秒钟（但我们可以假设大多数情况下为1秒），通过查看输入约束，可能可以猜测裁判的期望，即比O(N ^ 2)更快的算法。 - nhahtdh