题面链接
简要题意
求 \(\displaystyle{\sum_{i=1}^n\lvert p_i-i\rvert}=\) 冒泡排序最少交换次数的排列 \(\{p_n\}\) 的数量。
Lemmas
Lemma 1:冒泡排序最少交换次数等于逆序对数量
证明
考虑冒泡排序的过程交换一次逆序对减少一易证。
求 \(\displaystyle{\sum_{i=1}^n\lvert p_i-i\rvert}=\) 冒泡排序最少交换次数的排列 \(\{p_n\}\) 的数量。
考虑冒泡排序的过程交换一次逆序对减少一易证。