← 返回题目列表

AtCoder · joi2013ho5

5. 冒泡排序

中文机器翻译题面 查看原题

配点: 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' 时必须执行交换。