这是编程竞赛(已结束)的问题.我正在努力解决这个问题,但找不到一个健康的方法来解决这个问题.
问题如下:
IIIT Allahabad将于10月1日至5日庆祝其年度Techno-Cultural Fiesta Effervescence 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
我对这个问题几乎一无所知.有人可以解释问题背后的逻辑!!
问题是一个非常"经典"的竞争性编程问题,它计算了数组中的反转.反演被定义为一对(i,j),其中i <j且A [i]> A [j].
最通用的版本,其中给出了任意数字的数组,并且要求您计算反转的数量,通过修改合并排序算法来获得O(n log n)解决方案.
一个更受限制的版本^,其中数组中的最大值有合理的上限(请注意,这不是数组的长度),可以在O(n log m)中求解,其中m是最大值在数组中.这里的要点是你必须编写的代码量远远少于合并排序方法.
问题中的问题是计算交换次数以将数组排序为某个顺序,可以将其重建为计算交换次数以按升序对数组进行排序,并将其归结为计算反转次数.为什么反转次数？因为每次交换2个相邻元素时最多只能解决一次反转.
您需要创建一个数组,该数组描述相对于最终设置的框的当前位置.然后算法可以开始:
构造一个长度为m 的Fenwick Tree(二叉索引树)(对于问题中的问题,m = n).
我们将使用Fenwick树来帮助我们计算数组中大于当前元素的前面元素的数量.我们将保持到目前为止遇到的数字的频率,并使用Fenwick树范围求和查询来获得小于当前元素的元素数量(并导出大于当前元素的元素数量).
循环遍历数组的n个元素:
在(*)步骤中累积的反转计数.
^问题清楚地表明元素是唯一的,因此上面的算法将起作用.我只是不确定唯一性是否是必要条件,或者可以修改算法以适应存在重复元素的情况.