题目链接

题意:求给定排列冒泡排序轮数。


逗比题... 首先烂大街结论: 

冒泡排序交换次数=逆序对数

冒泡排序轮数=单点逆序对数最大值

统计每个数前面有多少个数比自己大,在生成数据的同时顺便统计。

为什么代码里那么写是对的呢? 显然这么更新答案一定不会使答案更大。

会不会更小呢 如果一次交换了 i 和 x,可能会影响 i-x 的答案 使得一个较大的答案没被考虑到

设这个较大的答案取在 j,若 x<j 则肯定被换过来的 x 更优,否则对 j 的答案无影响

这里本来有图的... 懒得放了

 


一个非常弱的准退役OIER