题意:给定一个正整数n,和一个1-n的一个排列,每个数可以和旁边的两个数的任意一个交换,每交换一次总次数就要加一,问将这个排列转换成一个递增的排列需要多少次交换?
题意可以转换成求这个排列的逆序对数。
这里用树状数组来解决它。
树状数组的处理能力是很强的,对于要用它来解决的问题,关键就在于如何将题目的关键地方和你的树状数组C[]联系起来。
此题较为简单,应属树状数组的基本应用-单点更新,区间求和。
思路:我们要求的是这个排列的逆序对数,那么它就和它前面小于它的个数或者大于它的个数有关了,这两点我们能很好的利用的就是第一点,小于它的个数,因为我们只要知道某点前面小于它的个数Sum(i),那么接下来用当前它所在排列的位置j 减去Sum(i) 得到的就是在它前面大于它的数的个数,有多少个就有多少对逆序对,用个ans来统计就可以了。
现在问题来了,Sum(i)的求法关系到了C[i]它表示什么。我们如何设置C[i]使得Sum(i)求出来的值刚好是前面小于i的数的个数。
我们已经知道,树状数组的单点更新就是将某点的值更新一个值val,而且对于它的所有祖先节点都要进行更新。
这样我们可以想到,我们将树状数组的C[i]的i看出是要读入进来的n的一个排列里面的一个值,那么我开始从读入这个排列的时候,遇到一个数那么是不是我就要将i后面的每个数都要加一个1,因为它比它后面的每一个数都要小。而我们要求的Sum(i),就刚好表示前面小于i的个数。
至此我们已经知道了如何用树状数组求解这个问题了。
下面上代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define N 1001 int C[N]; int num[N]; int T; int Lowbit(int x){ return x&(x^(x-1)); } void add(int pos,int num) { while(pos <= N) { C[pos] += num; pos += Lowbit(pos); } } int Sum(int end) { int sum = 0; while(end > 0) { sum += C[end]; end -= Lowbit(end); } return sum; } int main() { int s, t, i, j, T, ans; while(~scanf("%d",&T)) { memset(C,0,sizeof(C)); memset(num,0,sizeof(num)); ans = 0; for(j = 0; j < T; j ++) {//因为第一个数前面比它小的数没有,所以j要从0开始 scanf("%d",&s); add(s+1,1); ans += j - Sum(s);//Sum(s)求的就是小于s的个数,j - Sum(s)就是前j个数中大于s的个数 } printf("%d\n",ans); } return 0; }