Problem5125--小H排序5125: 小H排序
Time Limit: 20.000 Sec Memory Limit: 256 MB
Submit: 22 Solved: 3
[Submit] [Status] [Web Board] [Creator:]Description
排序自古以来就是经典问题,小H对其也很有研究,现在给小H要给一个由n个互不相同的整数组成的序列排序,但是只能任意交换相邻的两个数字,并最终使其序列成为升序序列,请问最少的交换次数是多少?
Input
输入包含多组测试数据。每组输入第一行是一个正整数n(n<500000),表示序列的长度,当n=0时结束。
接下来的n行,每行一个整数a[i](0<=a[i]<=999999999),表示序列中第i个元素。
Output
对于每组输入,输出使得所给序列升序的最少交换次数。
Sample Input
5
9 1 0 5 4
3
1 2 3
0
Sample Output
6
0
Source/Category
[Submit] [Status]