#P6326. 「JOI 2013 Final」冒泡排序
「JOI 2013 Final」冒泡排序
题目描述
冒泡排序从左至右扫描数列,每当相邻两个数满足 时,就交换它们。重复扫描直到数列按非降序排列,记录排序过程中发生的交换总次数。
给定数列 ,请先选定两个不同下标,恰好交换一次这两个位置的元素,然后对所得数列做冒泡排序。求排序过程中交换次数的最小值。开头所做的一次交换不计入答案,所选两个位置可以相距任意远,其数值也可以相同。
输入格式
第一行一个整数 。接下来 行,第 行包含整数 。
输出格式
输出一行一个整数,表示排序过程的最少交换次数。
5
10
3
6
8
1
0
5
3
1
7
9
5
2
3
1
2
3
1
样例 3 的原数列已经有序,仍需先交换两个不同位置。
数据范围
本站评测保证 ,。
- 对于 的数据,,且各元素互异。
- 对于 的数据,,且各元素互异。
- 对于 的数据,各元素互异。