P1966:火柴排队题解

思路

我们首先把\(a,b\)输入进一个数据结构,并且对这两个序列以高度为关键字排序。我们先来写出一组样例排序后的样子(数组下标为原本的位置):\[\{1_3,2_1,3_2,4_4\}\]与\[\{1_3,2_2,3_1,4_4\}\]我们观察发现,显然我们可以进行离散处理。所以令\(mapping[]\)为离散数组,在两组排序后进行\(mapping[a[i].index] = b[i].index\),便可以完成离散化。问题便转换为b数组要完成多少次变换才能与a相同(因为我们已经进行了离散化处理,\(mapping[]\)便可以在\(n\)范围内)。我们可以想到使用计算逆序对个数来解决这个问题。问题迎刃而解。

继续阅读P1966:火柴排队题解