求出两个数组的输入顺序(就是依次编号)
现在,每一个数字都有两个顺序,如:6 2 4 8的大小顺序是3 1 2 4,输入顺序是1 2 3 4
如果输入:
4
8 5 3 7(大小顺序:4 2 1 3,输入顺序:1 2 3 4)
4 9 6 7(大小顺序:1 4 2 3,输入顺序:1 2 3 4)
为了使第二个数组的大小顺序成为4 2 1 3,我们应该让第二个数组的输入顺序为2 3 1 4,
而2 3 1 4就是要进行求逆序对的目标数组
看这篇题解就好:https://blog.csdn.net/c20180602_csq/article/details/53134423
//本质就是求逆序对个数
#include <bits/stdc++.h>
#define MOD 99999997
using namespace std;
typedef long long LL;
int n;
vector<vector<int>> matrixa(100010, vector<int>(2));
vector<vector<int>> matrixb(100010, vector<int>(2));
vector<vector<int>> matrix(100010, vector<int>(2));
int tmp[100010];
LL merge_sort(int l, int r)
{
if (l >= r)
return 0;
int mid = (l + r) >> 1;
LL res = (merge_sort(l, mid) + merge_sort(mid + 1, r)) % MOD;
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (matrix[i][1] <= matrix[j][1])
tmp[k++] = matrix[i++][1];
else
{
res += (mid - i + 1);
res %= MOD;
tmp[k++] = matrix[j++][1];
}
}
while (i <= mid)
tmp[k++] = matrix[i++][1];
while (j <= r)
tmp[k++] = matrix[j++][1];
for (int i = l, j = 0; i <= r; i++, j++)
matrix[i][1] = tmp[j];
return res;
}
int main(void)
{
cin >> n;
for (int i = 1; i <= n; i++)
{
scanf("%d", &matrixa[i][0]);
matrixa[i][1] = i;
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &matrixb[i][0]);
matrixb[i][1] = i;
}
sort(matrixa.begin() + 1, matrixa.begin() + n + 1);
sort(matrixb.begin() + 1, matrixb.begin() + n + 1);
for (int i = 1; i <= n; i++)
{
matrix[i][0] = matrixa[i][1];
matrix[i][1] = matrixb[i][1];
}
sort(matrix.begin() + 1, matrix.begin() + n + 1);
LL ans = merge_sort(1, n);
cout << ans;
return 0;
}