一维数组中的任意二元素交换最多只能将整个序列的逆序对数减少1
2020-12-13 05:58
标签：对象 一维数组 span 改变 数组 逆序对数 情况 之间 swap 这是对的，值得思考，毕竟应用不是太少（所以要说服自己，用的时候更有底气）。 设一序列\(a_1,a_2,\cdots,a_n\)，其中有\(a_i(1\leq i \leq n)\)。 假设要通过交换\(a_i\)与某个数的位置来减少逆序对的数量。 交换的对象分这么几类: 1.\(a_i\)后面比\(a_i\)小的数 2.\(a_i\)后面比\(a_i\)大的数 3.\(a_i\)前面比\(a_i\)小的数 4.\(a_i\)前面比\(a_i\)大的数 假设交换的对象是\(a_j\) 前置说明（i-j之间不包括i、j） 第一种情况: 由于i,j被swap过， \(a_i\)与且仅与\(i-j\)之间元素的相对位置发生改变，\(a_j\)同样。 那么逆序对数还要加上i-j之间比k大的数和i-j之间比j小的数，还要减上i-j之间比k小的数和i-j之间比j大的数。 到头来总逆序对数还是只减了1。 第二种情况： 由于i、j被swap过，同上，到头来逆序对数还是只加了1. 第三种情况： 第四种情况： 一维数组中的任意二元素交换最多只能将整个序列的逆序对数减少1 标签：对象 一维数组 span 改变 数组 逆序对数 情况 之间 swap 原文地址：https://www.cnblogs.com/tztqwq/p/11157749.html
显然减少一个逆序对数
显然增加一个逆序对数
同上，增加一个逆序对数
同上，减少一个逆序对数。
文章标题：一维数组中的任意二元素交换最多只能将整个序列的逆序对数减少1
文章链接：http://soscw.com/essay/32153.html