2016多校联合训练contest4 1012Bubble Sort

Bubble Sort

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 224 Accepted Submission(s): 147

Problem Description

P is a permutation of the integers from 1 to N(index starting from 1). Here is the code of Bubble Sort in 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;

After the sort, the array is in increasing order. ?? wants to know the absolute values of difference of rightmost place and leftmost place for every number it reached.

Input

The first line of the input gives the number of test cases T; T test cases follow. Each consists of one line with one integer N, followed by another line with a permutation of the integers from 1 to N, inclusive.
limits T <= 20 1 <= N <= 100000 N is larger than 10000 in only one case.

Output

For each test case output “Case #x: y1 y2 … yN” (without quotes), where x is the test case number (starting from 1), and yi is the difference of rightmost place and leftmost place of number i.

Sample Input

Sample Output

Case #1: 1 1 2
Case #2: 0 0 0
Hint



In first case, (3, 1, 2) -> (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3)
the leftmost place and rightmost place of 1 is 1 and 2, 2 is 2 and 3, 3 is 1 and 3
In second case, the array has already in increasing order. So the answer of every number is 0.

题意：比赛的时候两度理解错题目意思。。后来才发现题目的意思是给你一个1~n的排列,问冒泡排序过程中,数字i(1<=i<=n)所到达的最左位置与最右位置的差值的绝对值是多少

参考了一下别人的，整理了一下思路，如下

判断一个数字到达的最左位置，可以打个草稿，会发现就min(a[i],i);

i是当前所在位置，a[i]为排序后的最终位置；

到达的最右位置就是当前位置i+他右边比他小的数的个数，N为100000，可以用树状数组来做

从右到左找,每个数a[i],我们只需判断它右边1~a[i]-1中有几个比他小数

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 100001;
int a[N],l[N],r[N],c[N];
int lowbit(int t)
{
    return t&(-t);
}
void update(int i,int x)
{
    while(i<N)
    {
        c[i]=c[i]+x;
        i+=lowbit(i);
    }
}
int Sum(int n) //求1-n-1项的和.
{
    int sum=0;
    while(n>0)
    {
         sum+=c[n];
         n-=lowbit(n);
    }
    return sum;
}
int main()
{
    int t,n,p=1,i;
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            l[a[i]]=min(i,a[i]);
        }
        for(i=n;i>0;i--)
        {
            r[a[i]]=i+Sum(a[i]-1);
            update(a[i],1);
        }
        printf("Case #%d:",p++);
        for(i=1;i<=n;i++)
            printf(" %d",abs(l[i]-r[i]));
        puts("");
    }
    return 0;
}

View Code