历届试题小朋友排队（树状数组求逆序数）

青旅半醒 2022-09-30 15:52 150阅读 0赞

问题描述

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。  
  
　　每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。  
  
　　如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。  
  
　　请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。  
  
　　如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数n，表示小朋友的个数。  
　　第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。

输出格式

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

样例输入

3  
3 2 1

样例输出

样例说明

首先交换身高为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。

题解：求每个数的逆序数对不高兴度的贡献就可以了。比如样例3 2 1。

每个数的逆序数为：2, 2, 2。那么就是(1+2)+(1+2)+(1+2)=9。

转化成求逆序数问题。

上树状数组或者归并排序都可以。只要不暴力即可。

代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1000000+5;
    const int N=100000+5;
    int a[maxn];
    int c[maxn];
    ll b[maxn]; 
    int n;
    int lowbit(int x)
    {
    	return -x&x;
    }
    int add(int x,int v)
    {
    	for(int i=x;i<maxn;i+=lowbit(i)){
    		c[i] += v; 
    	}
    }
    int query(int x)
    {
    	int sum=0;
    	for(int i=x;i>0;i-=lowbit(i))
    	{
    		sum += c[i];
    	}
    	return sum;
    }
    int main()
    {
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>a[i];
    		//将每个小盆友的身高加1然后作为树状数组的下标，将数值1存到相应的位置 
    		add(a[i]+1 , 1);//树状数组是从1开始的，而题目中小盆友的身高可以为0
     
    		b[i] +=(i+1)-query(a[i]+1); //前面比a[i]+1大的数的个数 = 当前输入数据量 - 输入的数据中小于等于当前的数的个数 
    	} 
    	//for(int i=0;i<n;i++)cout<<b[i]<<" ";
    	//cout<<endl; 
    	memset(c,0,sizeof(c));//把数状数组清空 
    	for(int i=n-1;i>=0;--i)
    	{
    		add(a[i]+1 , 1);
    		b[i]+=query(a[i]); //后面比在a[i]小的数的个数 = (倒着求)输入的数据中小于当前的数的个数  
    	}
    	//for(int i=0;i<n;i++)cout<<b[i]<<" ";
    	//cout<<endl;
    	ll ans=0;
    	ll sum=0;
    	for(int i=0;i<n;i++)
    	{
    		sum=b[i]; //每个数要进行交换的次数 
    	//	cout<<b[i]<<" ";
    		ans += (sum+1)*sum/2;
    	}
    	//cout<<endl;
    	cout<<ans<<endl;
    	return 0;
    }