心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
求逆序对个数。我是用离散化+树状数组做的。
以下是我的代码:
/*
 * Author:  lee1r
 * Created Time:  2011/8/5 23:33:01
 * File Name: poj2299.cpp
 
*/
#include
<iostream>
#include
<sstream>
#include
<fstream>
#include
<vector>
#include
<list>
#include
<deque>
#include
<queue>
#include
<stack>
#include
<map>
#include
<set>
#include
<bitset>
#include
<algorithm>
#include
<cstdio>
#include
<cstdlib>
#include
<cstring>
#include
<cctype>
#include
<cmath>
#include
<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef 
long long int64;
typedef unsigned 
long long uint64;

const int kMaxn(500007);

struct Type
{
    
int id,value,num;
};

bool cmp1(const Type &a,const Type &b)
{
    
return a.value<b.value;
}

bool cmp2(const Type &a,const Type &b)
{
    
return a.id<b.id;
}

int n,bit[kMaxn];
Type r[kMaxn];
int64 ans;

void Add(int x,int delta)
{
    
for(int i=x;i<=n;i+=lowbit(i))
        bit[i]
+=delta;
}

int Sum(int x)
{
    
int re(0);
    
for(int i=x;i>0;i-=lowbit(i))
        re
+=bit[i];
    
return re;
}

int main()
{
    
//freopen("data.in","r",stdin);
    
    
while(scanf("%d",&n)==1 && n)
    {
        
for(int i=1;i<=n;i++)
        {
            scanf(
"%d",&r[i].value);
            r[i].id
=i;
        }
        sort(r
+1,r+n+1,cmp1);
        
for(int i=1;i<=n;i++)
            r[i].num
=i;
        sort(r
+1,r+n+1,cmp2);
        
        ans
=0;
        memset(bit,
0,sizeof(bit));
        
for(int i=1;i<=n;i++)
        {
            Add(r[i].num,
1);
            ans
+=i-Sum(r[i].num-1)-1;
        }
        
        cout
<<ans<<endl;
    }
    
    
return 0;
}
posted on 2011-08-05 23:44 lee1r 阅读(250) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

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