基础算法题——小朋友排队（树状数组）

傷城~ 2023-07-19 10:58 8阅读 0赞

### 小朋友排队 ###

问题描述  
　　n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。  
输入格式  
　　输入的第一行包含一个整数n，表示小朋友的个数。  
　　第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。  
输出格式  
　　输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。  
样例输入  
3  
3 2 1  
样例输出  
9  
样例说明  
　　首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。  
数据规模和约定  
　　对于10%的数据， 1<=n<=10；  
　　对于30%的数据， 1<=n<=1000；  
　　对于50%的数据， 1<=n<=10000；  
　　对于100%的数据，1<=n<=100000，0<=Hi<=1000000。

--------------------

#### 题目分析 ####

暴力枚举：判断每一个元素右边有多少个元素小于本身，再判断每一个元素左边有多少个元素大于本身，得到每个元素的交换次数。用这种解法，只能得到30%的分数。  
这里就可以引出今天我们的重头戏——**树状数组**

应用场景：快速求区间和、前缀和  
①、前缀和数组（静态数组）  
新开一个数组b：每一个元素为对象数组a初始到目前的和  
eg:b\[0\]=a\[0\] b\[1\]=a\[0\]+a\[1\] … b\[10\]=a\[0\]+…+a\[10\]  
这里有个弊端：如果a数组中a\[10\]变化了，那b\[10\]到末尾的数据都要改。  
时间复杂度会大大增加。

②、性能优化：树状数组（动态数组）[树状数组参考资料][Link 1]  
![树状数组][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
每更新a数组维护一个C数组。  
更新 updata：(向后，影响C数组后面的部分元素)  
C\[k\]的含义是数组a上某个区间(k-lowbit(k),k\]和  
ps:lowbit(k)是k二进制最右边的1代表的整数  
lowbit(整数k)=k转换为二进制后最右边的1代表的整数  
lowbit(6)=2 ps:6的二进制为110  
C6=sum(4,6\]=a\[5\]+a\[6\]  
维护C数组：利用二进制每次移动就倍增的特点  
假设C\[index\]被改动，影响了C\[index+lowbit(index)\]  
C\[index+lowbit(index)\]被改动，影响C\[index+lowbit(index)+lowbit(index+lowbit(index))\]  
…  
当index为奇数时，本身C\[index\]不会被影响  
当index为2n时，C\[2k\]都会被影响（k>n）

获取 getSum:（向前，得到C数组前面部分元素和）  
计算前11项和sum11=C\[10\]+C\[8\]=C\[1010\]+C\[1000\]  
计算前13项和sum13=C\[12\]+C\[8\]=C\[1100\]+C\[1000\]  
计算前15项和sum15=C\[14\]+C\[12\]+C\[8\]=C\[1110\]+C\[1100\]+C\[1000\]  
计算第12项到第15项的和(不包含第12项)  
sum=sum15-sum11  
=C\[14\]+C\[12\]+C\[8\]-(C\[10\]+C\[8\])  
=C\[1110\]+C\[1100\]+C\[1000\]-(C\[1010\]+C\[1000\])

树状数组的作用：快速求出区间和  
树状数组本身没有意义，只有在a数组中才用实际意义

int lowbit(int n)
    { 
    	return n&(-n);//取n二进制下最右边的1 
    } 
    
    void updata(int n, int i, int v, int *c)//添加 向后 
    { 
    	for(int k=i; k<=n; k+=lowbit(k))
    	{ 
    		c[k]+=v;//影响c数组中部分元素 
    	}
    } 
    
    int getSum(int *c, int i)//获取 向前 
    { 
    	int sum=0;
    	for(int k=i; k >= 1; k-=lowbit(k))
    	{ 
    		sum+=c[k];
    	}
    	return sum;
    }

以上就是对树状数组应用的大致描述，若仍不太理解，可点击上面的参考链接。

--------------------

好了，接下来就是如何将树状数组应用到该题中呢？  
通过观察题目，我们知道每个小朋友最终不高兴值与他的交换次数是有关系的  
例如：t小朋友交换了4次，那他的不高兴值t\_ans=1+2+3+4=10  
我们只要求出每个小朋友交换次数就能够得到每个小朋友的不高兴值，从而得到全部小朋友的不高兴值。

思维突破：用树状数组c去维护身高数组a  
树状数组：**方便**我们统计每个身高交换次数

第一步：  
每放入a数组一个数据，更新树状数组c

第二步：  
c数组置零  
在a数组首向左看  
min n含义：在已加入的元素中，下标n左侧小于等于n的元素个数  
sum：已加入的元素个数  
cnt\[n\]存放sum-min n （在n的左侧，n与比它大的元素交换次数）

第三步：  
c数组置零  
在a数组尾向右看  
min n含义：在已加入的元素中，下标n右侧小于等于n的元素个数  
sum：已加入的元素个数  
cnt\[n\]存放min n（在n的右侧，n与比它小的元素交换次数）

第四步：  
利用ans统计全部不高兴值。

注意：  
①、a数组实际被c数组的反映出来的。**c数组是描述a数组**，a数组可以不被创建，我们要统计a数组的区间和，通过c数组即可实现。  
②、来回扫描。对于一个元素来说，前面比它大的一定要和它交换，而后面比它小的也一定要和它交换，这里通过来回扫描的方式，记录每个元素**总交换次数**。  
③、树状数组是没利用c\[0\]的，第一个元素为c\[1\] 。在本题中，0<=h\[i\]<=1000000，h\[i\]的取值范围对应树状数组的下标，1<=h\[i\]+1(下标)<=1000001 。

代码实现：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll lowbit(ll n)
    { 
    	return n&(-n);;
    }
    
    void updata(ll n, ll i, ll v, ll *c)
    { 
    	for(ll k=i; k<=n; k+=lowbit(k))
    	c[k]+=v; 
    }
    
    ll getSum(ll i, ll *c)
    { 
    	ll sum=0;
    	for(ll k=i; k>0; k-=lowbit(k))
    		sum+=c[k];
    	return sum;
    }
    
    ll h[100000];
    ll c[1000000+1];
    ll cnt[100000];	//存储每个小朋友的交换次数
    int main()
    { 
    	ll n, maxH=0;
    	cin>>n;
    	memset(cnt, 0, sizeof(cnt));
    	for(ll i=0; i<n; i++)
    	{ 
    		cin>>h[i];
    		if(maxH<h[i])
    			maxH=h[i];
    	}
    	
    	//注意：树状数组是没用c[0]的，第一个元素为c[1] 
    	//在本题中，0<=h[i]<=1000000
    	//h[i]的取值范围对应树状数组的下标
    	//1<=h[i]+1(下标)<=1000001 
    	//向右扫描 
    	memset(c, 0, sizeof(c));
    	for(ll i=0; i<n; i++)
    	{ 
    		updata(maxH+1, h[i]+1, 1, c);
    		int min=getSum(h[i]+1, c);
    		cnt[i]+=(i+1)-min;
    	}
    	//向左扫描
    	memset(c, 0, sizeof(c));
    	for(ll i=n-1; i>=0; i--)
    	{ 
    		updata(maxH+1, h[i]+1, 1, c);
    		cnt[i]+=getSum(h[i],c);
    	}
    	
    	long long ans=0;
    	for(int i=0; i<n; i++)
    	{ 
    		ans+=(cnt[i]*(cnt[i]+1))/2;//等差求和 
    	}
    	cout<<ans;
    	
    	return 0;
    }

##### 总结 #####

总在感叹前辈算法设计的巧妙，树状数组适合用于求数组在动态变化的情况下求区间和，相对于平常求前缀和，树状数组使算法效率得到了极大提升。

[Link 1]: https://www.cnblogs.com/xenny/p/9739600.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: /images/20230528/65c722e6b28642f68a2b940943a8532c.png