Skip to content

1301: Bubbling bubbles

题目

题目描述

给定一个长度为 $n$ 的排列,元素标号为 $1 \dots n$。

如果对这个排列进行冒泡排序,那么每个元素会被交换若干次。

请输出每个元素在进行冒泡排序时,参与了多少次交换。

我们将以以下代码为标准计算交换次数。

cpp void bubble_sort(int a[], int n) { for (int i = 1; i < n; i++) { for (int j = 0; j < n - i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); } } // after i-th inner iteration, a[n - i] is correct } }

Input

请从 stdin 读入。

输入第一行一个正整数 $n (1 \leq n \leq 10^6)$ 。

第二行包含 $n$ 个空格隔开整数表示排列,第 $i$ 个数为排列第 $i$ 位 $a_i (1 \leq a_i \leq n)$。输入保证 $n$ 个数互不相同。

Output

请输出到 stdout 中。

输出一行 $n$ 个由空格隔开的数,第 $i$ 个数表示 $i$ 被交换了多少次。

Sample Input

txt 4 1 2 3 4

txt 4 4 3 2 1

txt 3 2 3 1

Sample Output

txt 0 0 0 0

txt 3 3 3 3

txt 2 1 1

Constraints

Time Limit: 1s

Memory Limit: 512MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!