相邻交换的最小数量 [英] Minimum number of adjacent swaps

问题描述

这是从网上笔试的问题之一。

This is one of the question from online written test.

这是（1 ... N）编号的图书已抵达仓库。

Books numbered from (1...N) have arrived to a warehouse.

说这些书是一本书i是present只本书的左侧是最好安排我+ 1（对所有i，1＆LT; = I＆LT; = N-1）而这本书N为present到书籍1.左侧[是！任何循环排序序列中是最好的安排]

The books are said to be best arranged if a book "i" is present only to the left of book "i+1" (for all i, 1 <= i <= N-1) and that book N is present to the left of book 1. [Yes! Any cyclic sorted sequence is a best arrangement]

收到书籍是随机order.Now你的任务是找到了一条实现上述的最佳安排所需的移动最小数量。

Books received are in a random order.Now your task is to find out the minimal number of moves required to achieve the best arrangement described above.

请注意，只有有效的举措是选择一对相邻的书籍，让他们互换位置。

Note that only valid move is to choose a pair of adjacent books and have them switch places.

例如，如果书最初的顺序3 5 4 2 1

For Example if the books were initially in the order 3 5 4 2 1

解决方案可

一个。第一个交换第二对书：{结果：3 4 5 2 1}

a. First swap the second pair of books: { result : 3 4 5 2 1 }

乙。交换最右边的一对：{结果：3 4 5 1 2}

b. Swap the rightmost pair: { result : 3 4 5 1 2 }

因此​​，在2举动，我们达到最佳的安排。

So, in 2 moves we achieve the best arrangement.

输入：

第1行：一个整数：N

Line 1: A single integer: N

行第2..N + 1：包含描绘氮书籍初始订单的书号

Lines 2..N+1: Contains the book numbers depicting the initial order of N books.

OUTPUT：

行1：上述举动表明，它需要得到书本到任何最好的安排的最低金额

Line 1: The minimum amount of moves that it takes to get the books into any best arrangement described as above .

Sample Input:

5 (means 5 books have arrived)

3 (Next 5 lines contain the initial order of books)

5

4

2

1

Sample Output:

2

我试过了，但没能找到解决方案this.First不过，我觉得，我将分阵列中的两个数组，然后我将适用于插入排序两个阵列但也不能正常工作。 请帮我找出一个算法中的这个问题。

I tried but not able to find out solution for this.First I though that i will divide the array in two arrays and then I will apply insertion sort on both the arrays but that is also not working. Please help me to find out a algo for this question.

推荐答案

N，1可序列中的任何地方。例如1..5，可能是3,4,5,1,2。因此，作为复杂的<一个第一个数字可能是1..5，即5倍href="http://stackoverflow.com/questions/15364607/given-an-array-of-integers-in-random-order-you-have-to-find-the-minimum-number-o">$p$pvious问题。所以，你必须做5次。使用排序算法，有一个可更换的比较功能。

N,1 can be anywhere in the sequence. eg 1..5, could be 3,4,5,1,2. So the first digit could be 1..5, ie 5x as complicated as Previous question. So, you'll have to do it 5 times. Use a sort algorithm that has a replaceable compare function.

因此​​，对于第3试验比较是： -

So for the 3rd test the compare would be:-

// returns <0, 0 or >0
int compare(a,b){
     return ((b+N-3)%N) - ((a+N-3)%N);
}

这篇关于相邻交换的最小数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！