2014
02-13

Sort it

You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

3
1 2 3
4
4 3 2 1 

0
6

http://acm.hdu.edu.cn/showproblem.php?pid=2689

#include<iostream>
using namespace std;
int c[1010],a[1010],n;
int lowbit(int x)
{
return x&(-x);
}
int sum(int x)
{
int sum=0;
while(x>0)
{
sum=sum+c[x];
x-=lowbit(x);
}
return sum;
}
void inster(int x,int i)
{
while(x<=n)
{
c[x]+=i;
x+=lowbit(x);
}
}
int main()
{
int i,b,s;
while(scanf("%d",&n)>0)
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
s=0;
for(i=1;i<=n;i++)
{
scanf("%d",&b);
inster(b,1);      //求b前面小于等于b的数有多少个
s+=i-sum(b);     //b前面大于b的数有多少个
}
printf("%d\n",s);
}
return 0;
}

1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks