首页 > ACM题库 > HDU-杭电 > hdu 2689 Sort it[解题报告]C++
2014
02-13

hdu 2689 Sort it[解题报告]C++

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;
}

 

解题转自:http://www.cnblogs.com/ziyi–caolu/archive/2012/11/22/2782744.html


  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