微軟100題（92）搗亂分子（即逆序對的題目）

1.多人排成一個隊列,我們認為從低到高是正确的序列,但是總有部分人不遵守秩序。 如果說,前面的人比後面的人高(兩人身高一樣認為是合适的), 那麼我們就認為這兩個人是一對“搗亂分子”,比如說,現在存在一個序列: 176, 178, 180, 170, 171 這些搗亂分子對為 <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,  那麼,現在給出一個整型序列,請找出這些搗亂分子對的個數(僅給出搗亂分子對的數目即可,不用具體的對) 要求： 輸入: 為一個檔案(in)，檔案的每一行為一個序列。序列全為數字，數字間用”,”分隔。 輸出： 為一個檔案(out)，每行為一個數字，表示搗亂分子的對數。 詳細說明自己的解題思路，說明自己實作的一些關鍵點。 并給出實作的代碼 ，并分析時間複雜度。 限制： 輸入每行的最大數字個數為100000個，數字最長為6位。程式無記憶體使用限制。

思路：尋找逆序對數目，對每一行的資料，應用邊歸并排序邊統計的算法可以優化複雜度

#include <iostream>
#include <vector>
using namespace std;

int InverseParisRes(vector<int> &data,vector<int> &copy,int start,int end);
int InverseParis(vector<int> &data)
{
	size_t num = data.size();
	int count = 0;
	vector<int> copy(num,0);
	for (size_t i = 0; i < num; ++i)
	    copy[i] = data[i];
	count = InverseParisRes(data,copy,0,num-1);

	return count;
}
int InverseParisRes(vector<int> &data,vector<int> &copy,int start,int end)
{
	if(start == end)
	{
		copy[start] = data[start];
		return 0;
	}
	int middle = (end - start)/2;
	int left = InverseParisRes(copy,data,start,start+middle);
	int right = InverseParisRes(copy,data,start+middle+1,end);
	int i = start + middle;
	int j = end,k = end;
	int count = 0;
	while (i >= start && j >= start+middle+1)
	{
		if(data[i] > data[j])
		{
			copy[k--] = data[i--];
			count += j-start-middle;
		}
		else
		{
			copy[k--] = data[j--];
		}
	}
	while (i >= start)
	    copy[k--] = data[i--];
	while (j >= start+middle+1)
		copy[k--] = data[j--];

	return left + right + count;
}

int main()
{
	int a[4]={7,5,6,4};
	vector<int> data(a,a+4);
	cout<<InverseParis(data)<<endl;
	
	return 0;
}