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]) 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 In
3,1,2
1,2,3,4,5
Sample Out
1
0
算法:不过是每一项的nBigger(前面比它值大的项数)的累加和
交换的话,只需考虑 较大值 和 较小值 的交换,反之显然只会增加inversion count.
测试代码:
#pragma once #include <iostream> #include <string> #include <vector> using namespace std; #define MAX_DIGITS 20 struct DATA_STRUCT { DATA_STRUCT(): nBigger(0),value(0) {} int nBigger; int value; }; typedef vector<DATA_STRUCT> DATA_ARRAY; void SwapInt(int& a, int& b); int SwapAndCalcInversion(DATA_ARRAY arrData, int pos1, int pos2); void RunQuest03() { DATA_ARRAY arData; cout<<"enter an array of integers separated by comma or space:"<<endl; string str; cin>>str; //extract real data int i = 0; while(i < str.length()) { char szNum[MAX_DIGITS] = {0}; while( i < str.length() && str[i] >= '0' && str[i]<='9') { char szCr[2] = {0}; szCr[0] = str[i++]; szCr[1] = '