蓝桥杯历届试题小朋友排队树状数组+逆序数

刺骨的言语ヽ痛彻心扉 2024-02-17 19:39 89阅读 0赞

分析：本题需要用到树状数组的知识，如果不是很清楚可以访问：http://www.cnblogs.com/zichi/p/4806998.html  
本题是一个找逆序数的问题，如3 2 1，3的逆序对3 2、3 1，对于2:3 2、2 1，对于1:3 1、2 1，为完成排序任何一对逆序对的两个元素都必须完成一次交换，于是每个小朋友都完成了两次交换。  
那么问题就是转换为求逆序对的个数了，题目输入数据太大，不可能暴力枚举，所以用到树状数组求解（时间复杂度logN）。需要注意一点是，题目中的身高可能为0，而树状数组下标是从1开始，所以参数传递用： 身高值+1；  
分两步走，首先是身高大于i的（序列中排在i之前的情况下），然后是身高小于i。比如说序列（3,2,1）中，以第二个人为例，在前面找身高比他高的只有3，在后面找身高比他矮的就只有1，因此他需要交换两次。  
1、Sum(i)表示身高小于等于i的人数总和，所以 身高大于i的人数=目前总人数-Sum(i)；-> num\[i\]=目前总人数-Sum(i+1);  
2、Sum(i),因为这步求的就是身高小于（不能等于了，想想为什么？）i的人数总和，所以 num\[i\]+=Sum(i);  
  
高兴程度求出来之后(num\[i\]),此时就该计算总和了，处理方法是：先预处理（俗称打表）tol\[\]将所有不高兴程度都算出来放在里面，然后相加就行了。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    const int max1=1e5+10;
    const int max2=1e6+10;
    int C[max2];
    long long tol[max1];  //打表 
    int num[max1]; //每个人的交换次数 
    int a[max1];  //输入的身高
    int n;
    
    void init(){
    	tol[0]=0;
    	for(int i=1;i<=max1;i++)
    	tol[i]=i+tol[i-1];
    }
    int lowbit(int i){
    	return i&(-i);
    }
    
    int Sum(int i){
    	int ans=0;
    	while(i){
    		ans+=C[i];
    		i-=lowbit(i);
    	}
    	return ans;
    }
    
    void add(int i){
    	while(i<=max2){
    		C[i]++;
    		i+=lowbit(i);
    	}
    }
    int main(){
    	init();
        while(scanf("%d",&n)==1){
        	memset(C,0,sizeof(C));
        	memset(num,0,sizeof(num));
        	for(int i=0;i<n;i++){
        		scanf("%d",&a[i]);
        		add(a[i]+1); //因为本题身高可以为0 
    			num[i]=(i+1)-Sum(a[i]+1); //身高大于a[i]+1的个数 
    		}
    		
    		memset(C,0,sizeof(C));
    		for(int i=n-1;i>=0;i--){
    		add(a[i]+1); 
    		num[i]+=Sum(a[i]);  //Sum(b[i])表示身高小于b[i]+1的个数 			
    		} 
    		
    		long long ans=0;
    		for(int i=0;i<n;i++){
    			ans+=tol[num[i]];
    		}
    		
    		printf("%lld\n",ans);     //long long 类型输出格式是lld ,开始写成ld，蠢哭！！！
    		//cout<<ans<<endl;
    	}	
    	return 0;
    }

如有不恰当的地方，欢迎指出，谢谢！

第二次遇见树状数组，就自己的理解做点总结吧！

1、运用二进制思想，式子： C\[i\]=A\[i\]+.......A\[i-lowbit(i)+1\] 。总共有lowbit(i)项；

先介绍什么是lowbit(i) 返回的值就是 i&-i （也就是i的二进制数最低位为1的权值），比如说6（0110）返回的值是2（0010）；也许会问i&-i怎么求？ 参数i为有符号整数型，-i通过求补码求得，如 0110 ->（1001）->（1010）：分别是（原码、反码、补码），正数的补码就是其原码；所以 i&-i 返回的就是 （0010）。

![675542-20150914140031867-399947421.png][]

2、树状数组拥有快速维护和查询功能,时间复杂度（logn）。

C的构成性质决定了，C\[0011\]只会直接影响C\[0100\]，而C\[0100\]只会直接影响C\[1000\]，两者之间的关系满足 ： i+=lowbit(i);

为什么C\[i\]=A\[i\]+.......A\[i-lowbit(i)+1\] 呢？，这是在于对C数组的维护工作决定的，因为它们之间存在这种直接影响，所以具有这种关系都会被维护，如A\[4\] ,首先维护C\[4\] ,然后通过关系 4+=lowbit(4);维护C\[8\];，当从A\[1\]倒A\[8\]对C数组维护完成就可以得到，C\[8\]=A1+A2+A3+.......A8;

下面是维护函数：

void add(int i,int j)\{

while(i<=n)\{

C\[i\]+=j;

i+=lowbit(i);

3、求和代码：

int Sum(int i)\{

int ans=0;

while(i)\{

ans+=C\[i\];

i-=lowbit(i);

如有不恰当的地方，欢迎指出，谢谢！