题面链接
简要题意
求 \(\displaystyle{\sum_{i=1}^n\lvert p_i-i\rvert}=\) 冒泡排序最少交换次数的排列 \(\{p_n\}\) 的数量。
Lemmas
Lemma 1：冒泡排序最少交换次数等于逆序对数量
证明
考虑冒泡排序的过程交换一次逆序对减少一易证。
P4769[NOI2018 冒泡排序] 题解
发布时间 2023-03-23 11:23:10作者: Watware
求 \(\displaystyle{\sum_{i=1}^n\lvert p_i-i\rvert}=\) 冒泡排序最少交换次数的排列 \(\{p_n\}\) 的数量。
考虑冒泡排序的过程交换一次逆序对减少一易证。