d542.
10810 - Ultra-QuickSort
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
公開 測資點#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
(碼畜)
]
| ID | User | Problem | Subject | Hit | Post Date |
| 30550 |
|
d542 | 590 | 2022-05-28 23:13 | |
| 24060 |
|
d542 | 1384 | 2021-01-14 12:34 | |
| 16268 |
|
d542 | 1834 | 2018-12-14 18:00 |