[数据结构与算法]牛客 奇数码问题 题解 （归并排序求逆序对数 + 思路）

原题链接：https://ac.nowcoder.com/acm/contest/1001/F

每一个逆序对数都要超出int的范围么，一个变量类型让我一下午两道题wa了好几遍，就离谱…

解题思路：把每个数码矩阵看做一维数组（0不算），当这两个矩阵的逆序对数相同时，表示可以相互变换

原理推导：0左右移动不会改变逆序对数，上下移动相当于将某个数z向后（前）移动了（n - 1）位，此时逆序对数的奇偶性不变，所以如果两个矩阵的逆序对数奇偶性相同，则可以互相转换

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

const int N = 505 * 505;

int n;
int q1[N], temp[N], q2[N];
long long z1, z2;
bool flag1, flag2;

int merge_sort(int q[], int l, int r){
	if(l >= r) return 0;
	int mid = (l + r) >> 1;
	int rv = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	while(i <= mid && j <= r){
		if(q[i] <= q[j]){
			temp[k ++ ] = q[i ++ ];
		}
		else{
			temp[k ++ ] = q[j ++ ];
			rv += mid - i + 1;
		}
	}
	while(i <= mid){
		temp[k ++ ] = q[i ++ ];
	}
	while(j <= r){
		temp[k ++ ] = q[j ++ ];
	}
	for(i = l, j = 0; i <= r; j ++ , i ++ ){
		q[i] = temp[j];
	}
	return rv;
} 

int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	while(scanf("%d", &n) != EOF){
		int k1 = 0, k2 = 0;
		for(int i = 0, k = 0; i < n * n ; i ++ ){
			int a;
			scanf("%d", &a);
			if(a) q1[k1 ++ ] = a;
		}
		z1 = merge_sort(q1, 0, n * n - 2);
		
		for(int i = 0; i < n * n ; i ++ ){
			int a ;
			scanf("%d", &a);
			if(a) q2[k2 ++ ] = a;
		}
		z2 = merge_sort(q2, 0, n * n - 2);

		if((z1 & 1) == (z2 & 1)){
			cout<<"TAK"<<endl;
		}
		else if((z1 & 1) != (z2 & 1)){
			cout<<"NIE"<<endl;
		}
	}
	return 0;
}