为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 274491
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

求逆序数,N个数,N<=500000,一开始没有仔细看题,上来就做,后来才发现数的范围是999999999。因为最多500000个数,所以数和数之间的间隔很大,可以处理一下,使数的间隔变小,然后使用树状数组统计某个数前边的比它大的数的个数。将所有的数放到一个结构体里,称作num,并增加一个成员id,然后按num递增排列,再另开一个数组给每个数重新编号,使数的范围都在N以内。然后就可以很自然的用树状数组做了。时间500ms。据说归并排序比这个要快。
1 #include<iostream>
 2 #include<algorithm>
 3 #define M 500001
 4 using namespace std;
 5 int c[M],aa[M],n;                   //aa数组为排序后重新编号用
 6 struct digit
 7 {
 8     int num,id;
 9 }a[M];                              //num为数的大小
10 bool cmp(digit a,digit b){
11     return a.num<b.num;
12 }
13 int lowbit(int t){                 
14     return t&(t^(t-1));
15 }
16 int sum(int t){
17     int total=0;
18     while(t>0){
19         total+=c[t];
20         t-=lowbit(t);
21     }
22     return total;
23 }
24 void update(int t,int key){
25     while(t<=n){
26         c[t]+=key;
27         t+=lowbit(t);
28     }
29 }
30 int main()
31 {
32     int i,j;
33     long long ans;
34     while(scanf("%d",&n),n){
35         memset(c,0,sizeof(c));
36         ans=0;
37         for(i=1;i<=n;i++){
38             scanf("%d",&a[i].num);
39             a[i].id=i;
40         }
41         sort(a+1,a+n+1,cmp);
42         aa[a[1].id]=1;                                 //最小的数编号为1
43         for(i=2;i<=n;++i){
44             if(a[a[i].id].num!=a[a[i-1].id].num)      //如果前后两个数不等,则编号为下标
45                 aa[a[i].id]=i;
46             else
47                 aa[a[i].id]=aa[a[i-1].id];            //否则编号与前一个相同
48         }
49         //for(i=1;i<=n;i++) printf("%d ",aa[i]);
50         for(i=1;i<=n;++i){
51             update(aa[i],1);
52             ans+=(sum(n)-sum(aa[i]));                 //每次累加该数前边比它大的数的个数
53         }
54         printf("%lld\n",ans);
55     }
56 }
posted on 2010-08-02 08:34 baby-fly 阅读(175) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理