历届试题 小朋友排队(第五届蓝桥杯省赛)【归并排序or树状数组求逆序数】 解题报告 Apare_xzc

历届试题 小朋友排队(第五届蓝桥杯省赛)【归并排序or树状数组求逆序数】 解题报告

xzc 2019/4/22 15:44 1105

题目链接：小朋友排队

题面：

问题描述

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。

分析：

  每个人交换的次数r[i]是他前面身高比他大的人数和他后面身高比他小的人数之和
  求出r[i]后每个人的不开心度为：(1+r[i])*r[i]/2 , 求和即可

求逆序数我们有两种方法

方法一：归并排序求逆序数

我的代码

/* Author: xzc 2019/4/22 姓名 试题名称 提交时间 代码长度 许智超 小朋友排队 04-22 15:22 1.313KB C++ 正确 100 187ms 32.89MB */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+4;
int r[maxn];
struct Node{
	int x,id;
}node[maxn],node2[maxn];
void MergeSort(Node * a,int left,int right)
{
	if(right-left<=1) return;
	int mid = (left+right)>>1;
	MergeSort(a,left,mid);
	MergeSort(a,mid,right);
	Node * t = new Node[right-left]; 
	int i=left,j = mid,cnt = 0;
	while(i<mid||j<right)
	{
		if(j==right||i<mid&&a[i].x<=a[j].x)
			t[cnt++] = a[i++];
		else
			r[a[j].id]+=mid-i,t[cnt++] = a[j++];
	}
	cnt = 0;
	for(int i=left;i<right;++i)
		a[i] = t[cnt++];
}
void MergeSort2(Node * a,int left,int right)
{
	if(right-left<=1) return;
	int mid = (left+right)>>1;
	MergeSort2(a,left,mid);
	MergeSort2(a,mid,right);
	Node * t = new Node[right-left];
	int i = mid-1,j = right-1,cnt = right-left-1;
	while(i>=left||j>=mid)
	{
		if(i==left-1||j>=mid&&a[j].x>=a[i].x)
			t[cnt--] = a[j--];
		else
			r[a[i].id]+=j-mid+1,t[cnt--] = a[i--];
	} 
	cnt = 0;
	for(int i=left;i<right;++i)
		a[i] = t[cnt++];
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out1.txt","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;++i)
		scanf("%d",&node[i].x),node[i].id = i,
		node2[i].x = node[i].x,node2[i].id = i;
	MergeSort(node,0,n);
	MergeSort2(node2,0,n);
	long long ans = 0;
	for(int i=0;i<n;++i)
		ans += 1ll*r[i]*(r[i]+1)/2;
	printf("%lld\n",ans);
	
	
	return 0;
}

方法二：树状数组求逆序数

我的代码

/* 2019/4/22 Author : xzc problem: 蓝桥杯第五届省赛： 小朋友排队 state : AC 树状数组求逆序数 许智超 小朋友排队 04-22 11:00 770B C++ 正确 100 140ms 12.39MB */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int a[maxn],c[maxn],r[maxn],n,maxx; 
inline int lowbit(int x){return x&(-x);}
void update(int x,int add)
{
	while(x<=maxx) c[x]+=add,x+=lowbit(x);
}
int getSum(int x)
{
	int ans = 0;
	while(x>0) ans+=c[x],x-=lowbit(x);
	return ans;
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("ans.txt","w",stdout); 
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%d",a+i),a[i]+=2,maxx=max(maxx,a[i]);
	for(int i=1;i<=n;++i) //前面比它大的 
	{
		update(a[i],1);
		r[i] += i - getSum(a[i]);
	}
	for(int i=1;i<=n;++i) cout<<r[i]<<" ";cout<<endl; 
	memset(c,0,sizeof(c));
	for(int i=n;i>=1;--i) //后面比它小的 
	{
		update(a[i],1);
		r[i] += getSum(a[i]-1);
	}
	for(int i=1;i<=n;++i) cout<<r[i]<<" ";cout<<endl; 
	long long ans = 0;
	for(int i=1;i<=n;++i)
		ans += 1ll*r[i]*(r[i]+1)/2;
	printf("%lld\n",ans);
	
	return 0;
}