随笔 - 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 英雄哪里出来 阅读(1145) 评论(0)  编辑 收藏 引用 所属分类: 树状数组


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