7004 - 交換排序   

Description

排序是電腦科學裡面重要的一個東西。如果資料是排序好的話,幾乎每個問題都可以很有效率的解決。

市面上有一些很棒的排序演算法已經可以到達排序的下限O (n lg n)。

在這個問題我們想要討論的是一個新的排序方法。

在這個方法裡只有一個運算叫Flip,這個運算的動作是只能交換相鄰兩個數字。

給你一些數字。然後用Flip這個運算把這些數字由小排到大。

你必須找出最少要做這個運算幾次,才能把這些數字排好。

範例如下:

"1 2 3" --> 0次

"2 3 1" --> 2次

Input

輸入有多組測試資料。每組測試資料會給定一個N(N<=1000),代表有幾個數字。

下一行會有N個以空白隔開的整數,代表這N個數字。

輸入以EOF結束。

提示:讀測資可以用while (scanf("%d", &N) == 1)或while (scanf("%d", &N) != EOF)的方式讀取多組測資,以後不再提示這類輸入問題。

Output

對每組測試資料印出一行"Minimum exchange operations : M",M是最少翻轉的次數。

Sample Input  Download

Sample Output  Download

Tags




Discuss