配点: 100 点
冒泡排序是对列进行排序的一种算法, 1 一种。假设要将长度 N 序列 使用 A 的序列按升序排序。冒泡排序会检查相邻的 2 两个数,如果它们的大小关系混乱,就交换它们的位置。这是在从前往后依次遍历数列的过程中进行的。也就是说,A_i > A_{i + 1} 出现的位置, 2 交换这两个数,也就是这个意思,i = 1, 2, \ldots, N - 1 针对该顺序进行的操作是 1 次走查。通过将这次走查 N − 1 次重复,可以将数列按升序排序。
数列 A 的冒泡排序交换次数是指将上述算法应用于数列 A 时进行整数交换的次数。(众所周知,被称为冒泡排序的算法及其实现,在循环顺序、范围以及结束条件等方面存在细微差异。然而,已知在同一数列上应用时,整数的交换次数不会因这些差异而发生变化。)
例如,以下程序用 C 语言描述了长度为 n 的整数数组 a 通过冒泡排序进行排序的交换次数。
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 行が 1 回の整数の交換に相当 */
int x = a[j];
a[j] = a[j + 1];
a[j + 1] = x;
}
}
}
}
課題
长度 小于或等于 N 序列 使用 A 被给出。数列 A 在不同位置的 2 个整数 1 通过一次交换得到的数列 A' 假设这样构造。数列 A' 的冒泡排序最少交换次数的程序。 (第一次交换) 2 注意,交换的整数不一定是相邻的。)
制限
| 2 \leqq N \leqq 100\,000 | 数列 A 的长度 |
| 1 \leqq A_i \leqq 1\,000\,000\,000 | 数列 A 所含数字的大小 |
(注)过去在移植时对否定进行了修改。
入力
从标准输入读取以下数据。
- 1 行表示整数 N 上写着。N 是一个数字序列 它是 A 的长度。
- 继续 N 行中的 i 行目 (1 \leqq i \leqq N)上写有整数 A_i ,这表示数列的第 A 的 i 个整数。
出力
数字序列输出到标准输出。 A' 是一个整数,表示冒泡排序的最小交换次数。 输出为 1 行。
採点基準
评分数据中,分配的分数 10 对于%,N \leqq 1 000 和任何 i, j (1 \leqq i < j \leqq N) 关于 A_i \neq A_j 满意。
评分数据中,分配的分数 30 对于%,N \leqq 5\,000 和任何 i, j (1 \leqq i < j \leqq N) 关于 A_i \neq A_j 满意。
评分数据中,分配的分数 80 对于 %,任意 第一个 i, j (1 \leqq i < j \leqq N) 关于 A_i \neq A_j 满意。
入力例 1
5 10 3 6 8 1
出力例 1
0
数列 A 第一个 10 和最后一个 如果我们决定交换 1 ,我们会得到序列 A' 是一个排序列,冒泡排序交换的次数为 0 变为。
入力例 2
5 3 1 7 9 5
出力例 2
2
数列 A 的 3 第 通过交换 7 和最后一个 如果我们决定交换 5 ,序列 A' 是 省略 3, 1, 5, 9, 7 变为。A' 的冒泡排序交换次数为 2 。
入力例 3
3 1 2 3
出力例 3
1
从头开始的编号顺序 即使 A 已排序,序列 创建 A' 时必须执行交换。