d542. 10810 - Ultra-QuickSort
Tags :
Accepted rate : 396人/525人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 15:20

Content

在這個問題中你必須去分析一個特別的排序演算法 Ultra-QuickSort。這個演算法要將 n 個不同的整數由小到大排序,所用的動作是在必要的時候將 相鄰 的 2 個數交換。對以下的輸入序列:

9 1 0 5 4

這個 Ultra-QuickSort 將會產生以下的輸出:

0 1 4 5 9

你的任務是算出 Ultra-QuickSort 最少需要用到多少次交換的動作,來將輸入的序列由小到大排序。

Input

輸入含有多組測試資料。

每組測試資料的第一列

有 1 個整數 n( n < 500000)

代表需要排序的整數有多少個

接下來的 n 列每列有一個整數 (0 <= a[i] <= 999999999)

代表要排序的數

當 n=0 時代表輸入結束

請參考 Sample Input

Output

對每一組測試資料輸出一列

最少需要用到多少次交換的動作

來將輸入的序列由小到大排序

Sample Input #1
5
9
1
0
5
4
3
1
2
3
4
4
3
2
1
0
Sample Output #1
6
0
6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 2.0s , <1K
公開 測資點#1 (10%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (30%): 2.0s , <1M
公開 測資點#4 (30%): 2.0s , <10M
Hint :

 * 中文翻譯 : Lucky貓

 * 測資有誤請通知

Tags:
出處:
UVa10810 [管理者: morris1028 (碼畜) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
30550 910048@gm.yh ... (無意凡) d542
590 2022-05-28 23:13
24060 a610196@gm.t ... (狂徒) d542
1384 2021-01-14 12:34
16268 freedom50199 ... (帥氣魔方生) d542
題目敘述有誤
1834 2018-12-14 18:00