Microsoft Online Test for Core Technical Positions 3: Reduce inversion count

Time Limit:10000ms
Case Time Limit:1000ms
Memory Limit: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.

Sample Input
Sample Output
如果本文对您生活或工作产生了积极影响,那我非常高兴。
如果您愿意为文章的内容或想法提供支持,欢迎点击下边的捐赠按钮,资助作者创作更多高价值高品质的内容。
支付宝捐赠
anyShare分享到:

发表回复