历届试题 小朋友排队 蓝桥杯

问题描述 　　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。

归并排序

分组

递归排序

合并：不断比较左右两组最小值，取较小者加入备用数组

用了紫书的模板

具体到这道题，每次取左边的最小值，右边取过的值都与它组成逆序对，同理右边。（不用考虑本组中的逆序对，之前的合并已经计算过了）

比较麻烦的是处理相同身高的两人，我开了二维数组，每个人自带计数器；合并时，两边最小值相同，左边那组最小值加入缓存数组。

memset耗时严重。

#include<stdio.h> int n; long long h[100010][2]={0}; long long temp[100010][2]={0}; void merge_sort(int begin,int end){ int p,q,i,j; if(end-begin>1){ int med=begin+(end-begin)/2; merge_sort(begin,med); merge_sort(med,end); p=begin; q=med; i=0; while(p<med||q<end){ if(q>=end||(p<med&&h[p][0]<=h[q][0])){ temp[i][0]=h[p][0]; temp[i][1]=h[p][1]+q-med; p++; i++; } else{ temp[i][0]=h[q][0]; temp[i][1]=h[q][1]+med-p; q++; i++; } } i=0; for(j=begin;j<end;j++){ h[j][0]=temp[i][0]; h[j][1]=temp[i][1]; i++; } } } int main(){ int i; long long sum=0; scanf("%d",&n); for(i=0;i<n;i++) scanf("%lld",&h[i][0]); merge_sort(0,n); for(i=0;i<n;i++) sum+=(h[i][1]+1)*h[i][1]/2; printf("%lld",sum); return 0;}

树状数组

类似于二分法构造树，即c[8]=c[4]+c[6]+c[7]+a[8]

掌握更新与求和操作

更新一次，求和一次时间复杂度最大等于树的高度log2（元素个数）

注意下标从1开始，从零开始无法进行更新操作

具体到这道题，构造一个底层数组，下标是身高，元素是身高出现的次数，然后从队伍的头开始往底层数组填数更新，这个元素的位置减去比它小的数就是它左边的逆序对数；

同理从尾开始。

重复元素，减掉就好了；不要只更新到最大身高。

#include<stdio.h> int size=1000010; int c[1000010]={0}; int b[1000010]={0}; long long reverse[1000010]={0}; int lowbit(int x){ return x&(-x); } void update(int pos,int num){ while(pos<=size){ c[pos]+=num; pos+=lowbit(pos); } } int getsum(int end){ int sum=0; while(end>=1){ sum+=c[end]; end-=lowbit(end); } return sum; } int main(){ long long sum=0; int i,n,a[100010]={0}; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); b[a[i]+1]++; //if(a[i]+1>size)size=a[i]+1; update(a[i]+1,1); reverse[i]+=i-1-(b[a[i]+1]-1)-getsum(a[i]); } memset(c,0,sizeof(c)); memset(b,0,sizeof(b)); for(i=n;i>=1;i--){ update(a[i]+1,1); b[a[i]+1]++; reverse[i]+=(n-i)-(b[a[i]+1]-1)-(getsum(size)-getsum(a[i]+1)); } for(i=1;i<=n;i++) sum+=(reverse[i]+1)*reverse[i]/2; printf("%lld",sum); return 0;}