【微軟2014實習生及秋令營技術類職位線上測試】題目3 : Reduce inversion count

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

<dl></dl>

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 &lt;= 50) be a sequence of n numbers. If i &lt; j and A[i] &gt; 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})=&gt;

{

 InversionCount({1, 3, 2}) = 1 &lt;-- swapping 1 with 3, decreases inversion count by 1

 InversionCount({2, 1, 3}) = 1 &lt;-- swapping 2 with 3, decreases inversion count by 1

 InversionCount({3, 2, 1}) = 3 &lt;-- swapping 1 with 2 , increases inversion count by 1

}

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

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

<dt>樣例輸入</dt>

<dd></dd>

<dt>樣例輸出</dt>

思路，此題采用的是暴力法，不過改進的一個地方是計算InversionCount的算法，采用的是合并排序，時間複雜度是O（nlogn）