序列中有多少个逆序对冒泡排序就需要多少次交换。
以下是我的代码：
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(1007);
int n,ans,bit[kMaxn];
void Add(int pos,int delta)
{
for(int i=pos;i<=n;i+=lowbit(i))
bit[i]+=delta;
}
int Sum(int pos)
{
int re(0);
for(int i=pos;i>0;i-=lowbit(i))
re+=bit[i];
return re;
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1)
{
ans=0;
memset(bit,0,sizeof(bit));
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
Add(t,1);
ans+=i-Sum(t-1)-1;
}
printf("%d\n",ans);
}
return 0;
}
posted on 2011-07-31 11:58
lee1r 阅读(289)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构