#P6326. 「JOI 2013 Final」冒泡排序

    ID: 5815 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-冒泡排序离散化树状数组消除被支配候选贡献法二分查找扫描线差分标记区间修改懒标记线段树

「JOI 2013 Final」冒泡排序

题目描述

冒泡排序从左至右扫描数列,每当相邻两个数满足 Ai>Ai+1A_i>A_{i+1} 时,就交换它们。重复扫描直到数列按非降序排列,记录排序过程中发生的交换总次数。

给定数列 AA,请先选定两个不同下标,恰好交换一次这两个位置的元素,然后对所得数列做冒泡排序。求排序过程中交换次数的最小值。开头所做的一次交换不计入答案,所选两个位置可以相距任意远,其数值也可以相同。

输入格式

第一行一个整数 NN。接下来 NN 行,第 ii 行包含整数 AiA_i。

输出格式

输出一行一个整数,表示排序过程的最少交换次数。

5
10
3
6
8
1
0
5
3
1
7
9
5
2
3
1
2
3
1

样例 3 的原数列已经有序,仍需先交换两个不同位置。

数据范围

本站评测保证 2≤N≤1052\le N\le10^5,1≤Ai≤1091\le A_i\le10^9。

  • 对于 10%10\% 的数据,N≤1000N\le1000,且各元素互异。
  • 对于 30%30\% 的数据,N≤5000N\le5000,且各元素互异。
  • 对于 80%80\% 的数据,各元素互异。

JOI 2012/2013 本选第 5 题原 PDF