心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
序列中有多少个逆序对冒泡排序就需要多少次交换。
以下是我的代码:
#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 阅读(303) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理