【题解】CF1918B Minimize Inversions

题目大意

给定两个长度均为 $n$ 的序列 $A,B$。你可以进行任意次如下操作：

• 选择两个正整数 $i,j \in [1,n]$，交换 $A_i,A_j$ ，再交换 $B_i,B_j$。

请最小化两个序列中逆序对个数之和。

解题思路

贪心方式：

先将 $A$ 序列由小到大排序，将 $B$ 以对应的下标重新排序，此时 $A$ 和 $B$ 的逆序对之和最小。

证明：

对于任意的两对元素 $a_i$ 和 $a_j$，$b_i$ 和 $b_j$，无论如何交换，他们之间对应的数永远是固定的，不难看出，每对数对于逆序对的贡献只有 $0$ 或 $1$ 两种，则交换两对数对于逆序对的影响有三种：

• 从贡献为 $0$ 到贡献为 $2$。

• 从贡献为 $2$ 到贡献为 $0$。

• 不变，贡献均为 $1$。

通俗来说，只要让每对下标 $i$ 和 $j$ 中最多只有 $1$ 个贡献，那么任何一对数的贡献都不会多于交换后的贡献。

那么应该如何做到呢，贪心的核心就在于排序，让 $A$ 序列由小到大排序，$A$ 中就不存在逆序对了，$B$ 中最多只有 $1$ 个贡献，此时 $B$​ 中的逆序对便是答案。

AC Code

1
2
3
4
5
6
7
8
9

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i].first;
    for (int i = 1; i <= n; i ++ ) cin >> a[i].second;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i ++) cout << a[i].first << " \n"[i == n];
    for (int i = 1; i <= n; i ++) cout << a[i].second << " \n"[i == n];
}