随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

ZJU 1440 Bone Sort

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1440

/*
题意:
    给定N(N <= 10000)个互不相等的数字ai,要求求出进行至少多少
次交换操作,使得数列递增,并且输出原数列的逆序对的数目。

解法:
树状数组

思路:
    至少多少次交换可以采用贪心,每次找出数列中最小的那个数换到
它应该有的位置上,这一步可以采用hash,因为数字都不相同并且有可
能很大,事先离散化一下。求逆序数可以采用树状数组的区间求和,从
后往前线性扫描,每次统计比当前数小的sum和,然后将这个数插入到
树状数组中,n次循环过后,累加的值就是逆序数了。
*/

#include 
<iostream>
#include 
<algorithm>
#include 
<cstdio>
using namespace std;

#define ll long long
#define maxn 100010
int c[maxn], val[maxn], bin[maxn], n;
int pos[maxn];

int Binary(int val) {
    
int l = 1;
    
int r = n;
    
while(l <= r) {
        
int m = (l + r) >> 1;
        
if(bin[m] == val)
            
return m;
        
if(val > bin[m]) {
            l 
= m + 1;
        }
else
            r 
= m - 1;
    }

}


int lowbit(int x) {
    
return x & (-x);
}


void add(int pos) {
    
while(pos <= n) {
        c[pos] 
++;
        pos 
+= lowbit(pos);
    }

}

int sum(int pos) {
    
int s = 0;
    
while(pos > 0{
        s 
+= c[pos];
        pos 
-= lowbit(pos);
    }

    
return s;
}


int main() {
    
int i;
    
while(scanf("%d"&n) != EOF) {
        
for(i = 1; i <= n; i++{
            scanf(
"%d"&val[i]);
            bin[i] 
= val[i];
        }

        sort(bin
+1, bin+1+n);
        
for(i = 1; i <= n; i++{
            val[i] 
= Binary(val[i]);
        }

        
for(i = 1; i <= n; i++)
            c[i] 
= 0;

        ll ans 
= 0;
        
int swp = 0;
        
for(i = n; i >= 1; i--{
            ans 
+= sum(val[i]-1);
            add(val[i]);
        }

        
for(i = 1; i <= n; i++{
            pos[ val[i] ] 
= i;
        }


        
for(i = 1; i <= n; i++{
            
if(val[i] != i) {    
                swp 
++;
                
                
int pre = pos[i];
                
int nowVal = val[i];
                swap( val[ pre ], val[i] );

                pos[ nowVal ] 
= pre;
            }

        }

        printf(
"%d\n%lld\n", swp, ans);
    }

    
return 0;
}

posted on 2011-04-06 11:38 英雄哪里出来 阅读(1133) 评论(0)  编辑 收藏 引用 所属分类: 树状数组


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