BubbleSort

发布时间: 2017年11月12日 20:06   最后更新: 2017年11月12日 20:08   时间限制: 1000ms   内存限制: 512M

最近本能字学园新开始了程序设计课程,Matoi Ryuuko作为学园的学生也开始练习编程了。她使用C语言写出了这样一段冒泡排序代码:

for(int i=1;i<=N;++i)
    for(int j=N,t;j>i;—j)
        if(P[j-1] > P[j])
            t=P[j],P[j]=P[j-1],P[j-1]=t;

之后她使用这份代码给一个1~N的排列P进行排序,在排序之后,P变成了一个升序序列。现在她很好奇对于[1,N]中的每个整数 i,在排序过程(从还没对P进行任何操作开始到排序结束)中到达的最右位置-最左位置是多少。

第一行一个整数T,代表一共有T(1<=T<=20)组数据。接下来依次给出T组数据的内容。
每组数据的第一行是一个正整数N(1<=N<=100000),第二行是N个整数,保证是1~N的一个排列。

每组数据输出一行“Case #x: y1 y2 … yN”,其中x是测试数据的编号,yi=数字i的最右位置-最左位置。

复制
2
3
3 1 2
3
1 2 3
Case #1: 1 1 2
Case #2: 0 0 0

第一组数据的排序过程是这样的:(3, 1, 2) -> (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3),数字1,2,3到达的最左和最右位置分别是1和2,2和3,1和3。

第二组数据一开始就是有序的,所有数字的位置都没有变动。

排序 数据结构

2017 Fudan ACM-ICPC 程序设计校赛网络赛