排列之一個排列轉換成另一個排列 求逆序數（23）

1 問題

有一個排列A（元素無重複），經過一定步數的轉換，轉為排列B。交換A中第i個元素和第j個元素的代價為|i-j|。

輸入：

n   //元素個數

n個整數   //排列A

n個整數   //排列B

輸出：

一個整數    //需要的代價

2 分析

求兩個元素的逆序數，（如果大數在小數前面，則是一個逆序，4231逆序數為3+1+1=5），逆序數表示經過逆序數次轉換可以轉為有序數列，有序數列轉為目前狀态也需要逆序數步，是以求兩個數列的逆序數，然後做差。

3 代碼

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

int merge(int* arr, int* brr, int left, int right) {
	int r = 0;
	int mid = left + (right - left) / 2;
	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right) {
		if (arr[i] <= arr[j]) 		//構不成逆序,按降序排列
			brr[k++] = arr[j++];
		else{						//可以構成逆序
			brr[k++] = arr[i++];
			r += right - j + 1;		//j右邊所有的數都可以構成逆序
		}	
	}
	while (i <= mid)
		brr[k++] = arr[i++];
	while (j <= right)
		brr[k++] = arr[j++];
	for (i = left; i <= right; i++)
		arr[i] = brr[i];
	return r;
}

int cmergesort(int* arr, int* brr, int left, int right) {
	int r = 0;
	if (left < right) {
		int mid = left + (right - left) / 2;
		r += cmergesort(arr, brr, left, mid);
		r += cmergesort(arr, brr, mid + 1, right);
		r += merge(arr, brr, left, right);
	}
	return r;
}

void test() {
	int arr[6] = { 2,6,3,4,5,1 }; //1 4 1 1 1
	//int arr[6] = { 6,5,4,3,2,1 };
	//int brr[6];
	//int s = cmergesort(arr, brr, 0, 5);
	//cout << s << endl;
	int n;
	cin >> n;
	int* arr = new int[n];
	int* brr = new int[n];
	int* crr = new int[n];	//臨時數組
	for (int i = 0; i < n; i++) 
		cin >> arr[i];
	for (int i = 0; i < n; i++)
		cin >> brr[i];
	int s1 = cmergesort(arr, crr, 0, n - 1);
	int s2 = cmergesort(brr, crr, 0, n - 1);
	int r = 0;
	if (s1 > s2) 
		r = s1 - s2;
	else
		r = s2 - s1;
    delete[] arr;
    delete[] brr;
    delete[] crr;
	cout << r << endl;
}

int main() {
	test();
	//system("pause");
	return 0;
}