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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hy1004

题目描述

本题译自 JOI 2013 Final T5「バブルソート

冒泡排序是一种能对数列进行排序的算法。在使用冒泡排序对长为 N 的数列 A 进行升序排序时,如果相邻两个数中左边的数大于了右边的数,则交换这两个数的位置。每次从数列的前端开始扫描,当 A_i>A_{i+1} (i=1,2,\cdots,N-1) ,就将这两个数交换。扫描进行 N-1 次后,数列就一定满足升序排列。

对数列 A 进行冒泡排序的交换次数表示:对数列 A 进行以上所述算法时,整数被交换的次数。(冒泡排序的算法和实现包括循环顺序、范围和终止条件等。有时会存在细微差别。 但是,当应用于相同的数列时,整数的交换次数不会因这些情况的不同而改变。)

例如,以下为对长为 N 的整数数列 A 进行冒泡排序的程序(C 语言)。

void bubble_sort(int *a, int n) {
	int i, j;
	for (i = 0; i < n - 1; ++i) {
		for (j = 0; j < n - 1; ++j) {
			if (a[j] > a[j + 1]) {
				/* 以下 3 行相当于一次整数交换 */
				int x = a[j];
				a[j] = a[j + 1];
				a[j + 1] = x;
			}
		}
	}
}

任务

给出长为 N 的数列 A ,对数列 A 中任意两个整数进行一次交换得到数列 A' 。请编写程序求出对数列 A' 使用冒泡排序使其升序排列的交换次数的最小值。(请注意:开始时对数列 A 中整数的交换并不需要交换相邻两个数。)

输入格式

输入标准如下:

  • 第一行为一个整数 N ,表示数列 A 的长度;
  • 接下来的 N 行中的第 i (1 \leq i \leq N) 为一个整数 A_i ,表示数列 A 中第 i 个整数。

输出格式

输出一行一个整数:表示对数列 A' 进行冒泡排序的交换次数的最小值。

样例

样例输入 1

5
10
3
6
8
1

样例输出 1

0

样例说明 1

将数列 A 开头的 10 和最后的 1 交换,数列 A' 就已经是升序的了。冒泡排序的交换次数为 0

样例输入 2

5
3
1
7
9
5

样例输出 2

2

样例说明 2

将数列 A 3 个数 7 和最后一个数 5 交换,数列 A' 就成了 3,1,5,9,7 A' 的冒泡排序交换次数为 2

样例输入 3

3
1
2
3

样例输出 3

1

样例说明 3

虽然一开始数列 A 就是升序排列的,但是还是必须交换其中两个数构成数列 A'

数据范围与提示

对于 10\% 的数据:

  • N \leq 1000 且对于任意 i,j (1 \leq i < j \leq N) 满足 A_i \not = A_j

对于 30\% 的数据:

  • N \leq 5000 且对于任意 i,j (1 \leq i < j \leq N) 满足 A_i \not = A_j

对于 80\% 的数据:

  • 对于任意 i,j (1 \leq i < j \leq N) 满足 A_i \not = A_j

对于 100\% 的数据:

  • 1 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9