（Java實作） 光榮的夢想

光榮的夢想

Time Limit:10000MS Memory Limit:65536K

Total Submit:110 Accepted:45

Description

Prince對他在這片大陸上維護的秩序感到滿意，于是決定啟程離開艾澤拉斯。在他動身之前，Prince決定賦予King_Bette最強大的能量以守護世界、保衛這裡的平衡與和諧。在那個時代，平衡是個夢想。因為有很多奇異的物種擁有各種不穩定的能量，平衡瞬間即被打破。KB決定求助于你，幫助他完成這個夢想。

一串數列即表示一個世界的狀态。

平衡是指這串數列以升序排列。而從一串無序數列到有序數列需要通過交換數列中的元素來實作。KB的能量隻能交換相鄰兩個數字。他想知道他最少需要交換幾次就能使數列有序。

Input

第一行為資料的組數N。對于每組資料，第一行為數列中數的個數n,第二行為n <= 10000個數。表示目前數列的狀态。

Output

輸出一個整數，表示最少需要交換幾次能達到平衡狀态。

Sample Input

4

2 1 4 3

Sample Output

2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class guangrongdemengxiang {
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(),mid = 0,sum=0;
		int [] num = new int [n];
		for (int i = 0; i < num.length; i++) {
			num[i]=sc.nextInt();
			list.add(num[i]);
		}
		Arrays.sort(num);
		for (int i = 0; i < num.length; i++) {
			if(num[i]==list.get(i)) continue;
			for (int start = 0,end=num.length-1;;) {
				mid=(start+end)/2;
				if(num[mid]<list.get(i)){
					if(mid==start){
						start=end;
						continue;
					}
					start=mid;
					end=num.length-1;
				}
				else if(num[mid]>list.get(i)){
					start=0;
					end=mid;
				}
				else{
					int temp = list.remove(i);
					list.add(mid, temp);
					sum+=Math.abs(mid-i);
					break;
				}
			}
		}
		System.out.println(sum);
	}

}