【マイクロソフト2014実習生及び秋令営技術職オンラインテスト】テーマ3:Reduce inversion count

時間制限:
10000ms
単一点時限:
1000ms
メモリの制限:
256MB

Description

Find a pair in an integer array that swapping them would maximally decrease the inversion count of the array. If such a pair exists, return the new inversion count; otherwise returns the original inversion count.
Definition of Inversion: Let (A[0], A[1] ... A[n], n <= 50) be a sequence of n numbers. If i < j and A[i] > A[j], then the pair (i, j) is called inversion of A.
Example: Count(Inversion({3, 1, 2})) = Count({3, 1}, {3, 2}) = 2 InversionCountOfSwap({3, 1, 2})=> {  InversionCount({1, 3, 2}) = 1 <-- swapping 1 with 3, decreases inversion count by 1  InversionCount({2, 1, 3}) = 1 <-- swapping 2 with 3, decreases inversion count by 1  InversionCount({3, 2, 1}) = 3 <-- swapping 1 with 2 , increases inversion count by 1 }

Input

Input consists of multiple cases, one case per line.Each case consists of a sequence of integers separated by comma.

Output

For each case, print exactly one line with the new inversion count or the original inversion count if it cannot be reduced.

サンプル入力

3,1,2
1,2,3,4,5

サンプル出力

1
0

考え方、この問題は暴力法を採用しているが、改善された点はInversionCountを計算するアルゴリズムであり、合併ソートを採用しており、時間の複雑さはO(nlogn)である.

import java.util.Scanner;


public class Main {

	static int InversionCount ;
	
	public static void main(String[] args) 
	{
		int T,t;
		Scanner jin = new Scanner(System.in);
		while (jin.hasNext()) {
			String str = jin.next();
			String[] argstr = str.split(",");
			int[] num = new int[argstr.length];
			int[] tmp = new int[argstr.length];
			for (int i = 0; i < num.length; i++) {
				num[i] = Integer.parseInt(argstr[i]);
				tmp[i] = Integer.parseInt(argstr[i]);
			}
			InversionCount = 0;
			MergeSort(tmp, 0, tmp.length-1);
			int ret = InversionCount;
			for (int i = 0; i < num.length; i++)
				tmp[i] = num[i];
			for (int i = 0; i < num.length-1; i++) {
				for (int j = i+1; j < num.length; j++) {
					if (num[i] > num[j]) {
						int tmpnum = num[i];
						num[i] = num[j];
						num[j] = tmpnum;
						InversionCount = 0;
						MergeSort(num, 0, num.length-1);
						ret = Math.min(ret, InversionCount);
						for (int k = 0; k < num.length; k++)
							num[k] = tmp[k];
					}
				}
			}
			System.out.println(ret);
		}
	}
	
	public static void MergeSort(int[] array, int lhs, int rhs) {
		if (lhs < rhs) {
			int mid = lhs + ((rhs - lhs)>>1);
			MergeSort(array, lhs, mid);
			MergeSort(array, mid+1, rhs);
			Merge(array, lhs, mid, rhs);
		}
	}
	public static void Merge(int[] array, int lhs, int mid, int rhs) {
		int[] tmp = new int[rhs-lhs+1];
		int i = lhs, j = mid+1;
		int k = 0;
		while(i <= mid && j <= rhs)
		{
			if (array[i] > array[j]) {
				InversionCount += mid-i+1;
				tmp[k++] = array[j++];
			}
			else {
				tmp[k++] = array[i++];
			}
		}
		while(i <= mid)
		{
			tmp[k++] = array[i++];
		}
		while(j <= rhs)
		{
			tmp[k++] = array[j++];
		}
		for (i = 0; i < k; i++) {
			array[i+lhs] = tmp[i];
		}
		tmp = null;
	}
	
}