历届试题 小朋友排队(第五届蓝桥杯省赛)【归并排序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;
}
