HDU 1394 树状数组求逆序数

注释详细，如有疑惑请移步树状数组总结

/*求逆序数
  A[i]默认值为0，一个数加入序列使A[i]+=1，表示该数出现，求i的前缀和相当于求比i小的数的数目s
  那么比i大的数为n-1-s，n为加入该数后当前序列数量，用动态规划的方式一个个加入数求总逆序
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
const int N=5e3+10;
int c[N],A[N];
int n;
inline int read() {
	char ch=getchar();
	int s=0,w=1;
	while(ch<'0' || ch>'9') {
		if(ch=='-')	w*=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')	s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*w;
}
inline int lowbit(int i) {
	return i&(-i);
}
void update(int i,int x) { //通常使用为update( i , 1 )，即将数组A[i]的值加1  删除数字就是x=-1
	while(i<=N) {//有一个Bug，不能读0，为此，我们直接把每个数字+1处理	还有,范围要写N而不是n！逆序数的数组范围是N，是全区间！
		c[i]+=x;
		i+=lowbit(i);
	}
}
int sum(int i) { //求前缀和
	int s=0;
	while(i>0) {
		s+=c[i];
		i-=lowbit(i);
	}
	return s;
}
int main() {
	while(scanf("%d",&n)!=EOF) {
		int ans=0;
		memset(A,0,sizeof(A));
		memset(c,0,sizeof(c));
		for(int i=1; i<=n; i++) {
			A[i]=read()+1;
			ans+=i-1-sum(A[i]);
			update(A[i],1);
		}
		int temp=ans;//易错点：temp是动态更新且具有继承性的，ans仅仅记录最小值罢了，不能把这个语句放到for循环里 
		for(int i=1; i<n; i++) {
			//移走A[i]:update(A[i],-1) x=sum(A[i]) ans-=x;
			//加入A[i]:update(A[i],1) x=sum(A[i]) ans+=n-1-x;
			update(A[i],-1);//移走第一位数字A[i] 
			int x=sum(A[i]);//查询比A[i]小的，比第一位小的都对逆序有贡献 
			temp-=x;//减去贡献数 
			temp+=n-1-x;//不是i+1-x!这里序列已经完全加入了 
			if(ans>temp)	ans=temp;//ans大于temp时更新而不是小于！ 
			update(A[i],1);
		}
		printf("%dn",ans);
	}
	return 0;
}
/*
10
1 3 6 9 0 8 5 7 4 2
先求出数组逆序数：
A[i]默认值为0，一个数加入序列使A[i]+=1，表示该数出现，求i的前缀和相当于求比i小的数的数目s
那么比i大的数为n-1-s，n为加入该数后当前序列数量，用动态规划的方式一个个加入数求总逆序
然后进行n-1次操作
每次移走第一位数字，也就是A[i],加入它到最后一位
难点是如何获得移走第一位数字 对后面n-1个数的逆序数所带来的影响
事实上这并不难，相当于 求出全序列比第一位数字小的数s，asn-s即可
移走A[i]:update(A[i],-1) x=sum(A[i]) ans-=x;
加入A[i]:update(A[i],1) x=sum(A[i]) ans+=n-1-x;
*/

最后

以上就是舒服小鸭子为你收集整理的HDU 1394 树状数组求逆序数的全部内容，希望文章能够帮你解决HDU 1394 树状数组求逆序数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。