5

这是一个编程竞赛的问题（已经结束）。我一直在努力解决这个问题，但找不到一个健康的方法来解决这个问题。

问题如下：

IIIT Allahabad 将于 10 月 1 日至 5 日庆祝其一年一度的科技文化嘉年华 MM12。厨师已同意为这个节日供应糖果。厨师准备了 N 盒糖果，编号从 1 到 N（每个数字恰好出现一次）。厨师对盒子的布置非常讲究。他希望按特定顺序排列盒子，但不幸的是，厨师很忙。他让你为他重新安排箱子。给定盒子的当前顺序，您必须按照指定的顺序重新排列盒子。但是有一个限制。您只能交换两个相邻的框以达到所需的顺序。输出，所需的此类相邻交换的最小数量。

输入

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

输出

对于每个测试用例，输出一个整数“K”，需要最少的相邻交换次数。约束：

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

例子

输入：

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

我对这个问题几乎一无所知。有人可以解释一下问题背后的逻辑！！

4

5 回答 5

6

这个问题是一个相当“经典”的竞争性编程问题，它计算数组中的倒数。反转定义为一对 (i, j)，其中 i < j 且 A[i] > A[j]。

最通用的版本，给出了一个任意数字的数组，并要求您计算反转的数量，通过修改归并排序算法具有O(n log n) 解决方案。

一个更受限制的版本^，其中数组中的最大值有一个合理的上限（注意这不是数组的长度），可以在 O(n log m) 中求解，其中 m 是最大值在数组中。这里的要点是您必须编写的代码量远少于合并排序方法。

问题中的问题是关于计算交换次数以将数组排序到一定顺序，这可以重构为计算交换次数以对数组进行升序排序，归结为计算反转次数。为什么要反转次数？因为每次交换 2 个相邻元素最多只能解决一次反转。

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

  1. 构造一个长度为 m 的Fenwick 树（二叉索引树）（对于问题中的问题，m = n）。

    我们将使用 Fenwick 树来帮助我们计算数组中大于当前元素的前面元素的数量。我们将保持到目前为止遇到的数字的频率，并使用 Fenwick Tree 范围求和查询来获取小于当前元素的元素数（并导出大于当前元素的元素数）。

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

    • 使用范围求和查询来统计记录了多少小于当前数字的数字。
    • 使用上面的信息找出比当前数字大的数字。将此添加到反转计数。请注意不要包括正在考虑的元素。(*)
    • 在元素的值处调整 + 1 到 Fenwick 树。

  3. 在 (*) 步骤中累积的反转计数。

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

于 2012-09-30T05:31:35.000 回答
4

将源列表简化为 (1,2,...,N) 的排列。（通过将目标的逆应用于源）

然后计算反转次数。

IE

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 中的反转。

于 2012-09-30T05:06:16.837 回答
2

假设所需的顺序是数字的排序顺序，问题就归结为在数组中查找反转的数量。

如果且 ，则称Apair (i,j)是反演。这是因为相邻元素之间的每次（最佳）交换都将反转的数量减少了. 您可以通过与归并排序非常相似的分治算法找到倒数。这是C 代码的一个很好的解释。i < jarray[i] > array[j]1O(n log n)

编辑证明反转次数等于最佳交换次数：

让i成为 中的任何位置array。交换array[i]并将array[i+1]反转次数最多减少 1。因此所需的交换次数至少等于反转次数。另一方面，如果array未排序，我们总是可以找到一对(i, i+1)这样array[i] > array[i+1]（即是一个反转），并通过交换将反转的(i,j)数量减少 1 。因此，反转的数量等于交换的最小数量。array[i]array[i+1]

于 2012-09-30T05:05:39.107 回答
0

该问题可以被认为是一个反转计数问题，如下所示：

因为数字的优先级是按照我们应该排序的顺序给出的。

考虑优先级并将其替换为数字

例如：

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 在其右侧有 0 个小于 1 的元素。

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

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

2 右侧有 0 个小于 2 的元素。

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

现在可以使用此处讨论的反转计数来计算上述过程 http://www.geeksforgeeks.org/archives/3968。

注意：我得到的答案很有用，只是详细描述了整个事情。谢谢你

于 2012-09-30T05:42:51.953 回答
-1

我无法从数学上证明这一点，但是在 4/4 的测试用例中，您可以通过将框从最左边开始放在正确的位置（也可以从最右边开始）并向右移动来获得最小的交换。IE

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）。

于 2012-09-30T04:59:05.247 回答