这道题目看到题干就知道跟逆序对相关了
首先考虑最终的等式会是怎么样的
既然要成为同序和，我们将两个序列中值相同的连边，比如
那么最终我们要让所有边都是竖直的
由于很像逆序对，我们考虑这里的逆序对是什么
不难看出是有交叉，即用一个二元组\((x,y)\)描述一条边，其中\(x\)是\(a\)中的下标，\(y\)是\(b\)中的下标
那么就是序列中存在两个二元组\((x_1,y_1)\)和\((x_2,y_2)\)，满足\(x_1＜x_2\)且\(y_1＞y_2\)，那么这就贡献了一个逆序对
首先有逆序对肯定不是最终序列
我们再证明没有逆序对了一定是最终序列
在没有逆序对的序列中，由于不存在逆序对，所以对\((1,y_1)\)，\((2,y_2)\)，\((3,y_3)\)...\((n,y_n)\)，有\(y_n＞...＞y_3＞y_2＞y_1\)，根据抽屉原理，必有\(y_i=i\)，即都是竖直的边，所以就是最终序列
我们再来证明如果一个序列有逆序对，那么一定存在相邻逆序对
反证，如果不存在相邻逆序对，即对\((i,y_i)\)和\((i+1,y_{i+1})\)，有\(y_i＜y_{i+1}\)，那么对\(i\)赋值从\(1\)到\(n-1\)，由鸽巢原理可以得出不存在逆序对，与条件矛盾，所以一定有相邻逆序对
我们的一次操作显然最多使相邻逆序对减少一，所以每次选择相邻逆序对进行操作即可
但我不是很理解洛谷题解里面说的按照\(a\)关键字对\(b\)进行排序的意思
标签：...,那么,最终,排队,相邻,火柴,序列,逆序 From： https://www.cnblogs.com/dingxingdi/p/17904210.html