本文主要是介绍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;
}
这篇关于POJ2299 Ultra-QuickSort【树状数组】【逆序数】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
