POJ2299 Ultra-QuickSort【树状数组】【逆序数】

78 阅读 0 评论 52 点赞

我是靠谱客的博主欢喜白开水，最近开发中收集的这篇文章主要介绍POJ2299 Ultra-QuickSort【树状数组】【逆序数】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：

http://poj.org/problem?id=2299

题目大意：

给你一个包含N个整数的序列，只能通过交换相邻的数字，最终变为升序顺序，问：最少需要多少次交换。

思路：

其实就是问冒泡排序的交换次数。其实就是求原序列的逆序数。用归并排序、线段树、树状数组都可以做。

但是如果用线段树和树状数组来做的话，因为元素个数是500000，但是元素值范围却是999999999，需

要先离散化。这里用间接排序的方法。用一个数组Arr[]存放原序列的值，另一个数组Id[]存放原序列编号

(1~N)，对Id[]按Arr[]元素值的从大到小排序，得到Arr[]数组元素的相对大小排序(第几大的数)。然后再用

树状数组来求逆序数。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;

int Tree[500050],Arr[500050],Id[500050],N = 500050;

int cmp(const int x,const int y)
{
    return Arr[x] < Arr[y];
}

int Lowbit(int i)
{
    return i & (-i);
}

void Update(int i,int x)
{
    while(i <= N)
    {
        Tree[i] = Tree[i] + x;
        i += Lowbit(i);
    }
}

LL Query(int n)
{
    LL sum = 0;
    while(n > 0)
    {
        sum += Tree[n];
        n -= Lowbit(n);
    }
    return sum;
}

int main()
{
    int N;
    while(cin >> N && N)
    {
        memset(Tree,0,sizeof(Tree));
        for(int i = 1; i <= N; ++i)
        {
            cin >> Arr[i];
            Id[i] = i;
        }
        sort(Id+1,Id+N+1,cmp);  //间接排序，得到编号
//        for(int i = 1; i <= N; ++i)
//            cout << Arr[i] << ' ' << Id[i] << endl;

        LL ans = 0;
        for(int i = 1; i <= N; ++i) //求逆序数
        {
            Update(Id[i],1);
            ans += i - Query(Id[i]);
        }
        cout << ans << endl;
    }

    return 0;
}