Description
n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
Input
输入的第一行包含一个整数n，表示小朋友的个数。
第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。
第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。
Output
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
Sample Input
3 3 2 1
Sample Output
9
Hint
【样例说明】
首先交换身高为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的小朋友，再交换身高为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。
Source
蓝桥杯
对每个数字，求出前面比他大的数字个数+后面比他小的数字个数，就是需要该数字需要交换的次数
每个人的不开心度就是首项是1，尾项是交换次数，d=1的等差数列的和
所以就是对每个数字进行一次等差数列的求和:(a1+d)*an/2
所以我们的重点是统计每个数字需要交换的次数
开始想的是冒泡
但我们冒泡肯定会超时
所以采用树状数组
快很多！
每个人的不开心度就是首项是1，尾项是交换次数，d=1的等差数列的和
所以就是对每个数字进行一次等差数列的求和:(a1+d)*an/2
所以我们的重点是统计每个数字需要交换的次数
开始想的是冒泡
但我们冒泡肯定会超时
所以采用树状数组
快很多！
具体分析：
用一个计数数组，数组的下标存输入的数字，先从头开始遍历，出现一次就加一，输入一次就统计前面大于该数字的数出现的次数：当前数字的个数i-前面小于等于该数字的个数
所以树状数组和线段树都是可以的
code：
树状数组
没有离散化的代码：
#include<stdio.h> #include<iostream> #include<math.h> #include<string.h> #include<set> #include<map> #include<list> #include<math.h> #include<queue> #include<algorithm> using namespace std; typedef long long LL; #define INF 99999999 #define me(a,x) memset(a,x,sizeof(a)) int mon1[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; int getval() { int ret(0); char c; while((c=getchar())==' '||c==' '||c==' '); ret=c-'0'; while((c=getchar())!=' '&&c!=' '&&c!=' ') ret=ret*10+c-'0'; return ret; } void out(int a) { if(a>9) out(a/10); putchar(a%10+'0'); } #define max_v 1000005 LL a[max_v]; LL b[max_v]; LL c[max_v]; LL maxx; int n; int lowbit(int x) { return x&(-x); } void update(int x,int d) { while(x<=maxx) { c[x]+=d; x+=lowbit(x); } } int getsum(int x)//前面小于等于x的个数 { int res=0; while(x>0) { res+=c[x]; x-=lowbit(x); } return res; } int main() { while(~scanf("%d",&n)) { LL ans=0; memset(c,0,sizeof(c)); memset(b,0,sizeof(b)); maxx=0; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); a[i]++;//防止有0，都偏移一个单位不影响结果 maxx=max(maxx,a[i]); } for(int i=1;i<=n;i++)//先更新再统计 { update(a[i],1); b[i]+=((i-getsum(a[i])));//前面大于x的个数：当前数字个数i减去数列前面小于等于a[i]的数的个数 } memset(c,0,sizeof(c)); for(int i=n;i>=1;i--)//序列反向 { update(a[i],1); b[i]+=getsum(a[i]-1);//后面小于x的个数：小于等于a[i]-1的数的个数就是小于a[i]的数的个数 } for(int i=1;i<=n;i++) { ans+=((b[i]+1LL)*b[i]/2LL);//n个等差数列求和 } printf("%lld ",ans); } }
离散化的树状数组代码（离散化：数据范围压缩，但数据间的相对关系没有改变）
#include<stdio.h> #include<iostream> #include<math.h> #include<string.h> #include<set> #include<map> #include<list> #include<math.h> #include<queue> #include<algorithm> using namespace std; typedef long long LL; #define INF 99999999 #define me(a,x) memset(a,x,sizeof(a)) int mon1[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; int getval() { int ret(0); char c; while((c=getchar())==' '||c==' '||c==' '); ret=c-'0'; while((c=getchar())!=' '&&c!=' '&&c!=' ') ret=ret*10+c-'0'; return ret; } void out(int a) { if(a>9) out(a/10); putchar(a%10+'0'); } #define max_v 1000005 struct node { LL v,pos; }p[max_v]; bool cmp(node x,node y) { if(x.v!=y.v) return x.v<y.v; else return x.pos<y.pos; } LL b[max_v]; LL c[max_v]; LL n; int lowbit(int x) { return x&(-x); } void update(int x,int d) { while(x<=n) { c[x]+=d; x+=lowbit(x); } } int getsum(int x)//前面小于等于x的个数 { int res=0; while(x>0) { res+=c[x]; x-=lowbit(x); } return res; } int main() { while(~scanf("%lld",&n)) { LL ans=0; memset(c,0,sizeof(c)); memset(b,0,sizeof(b)); for(int i=1;i<=n;i++) { scanf("%lld",&p[i].v); p[i].pos=i; } sort(p+1,p+1+n,cmp);//离散化 for(int i=1;i<=n;i++)//先更新再统计 { update(p[i].pos,1); b[i]+=((i-getsum(p[i].pos)));//前面大于x的个数：当前数字个数i减去数列前面小于等于a[i]的数的个数 } memset(c,0,sizeof(c)); for(int i=n;i>=1;i--)//序列反向 { update(p[i].pos,1); b[i]+=getsum(p[i].pos-1);//后面小于x的个数：小于等于a[i]-1的数的个数就是小于a[i]的数的个数 } for(int i=1;i<=n;i++) { ans+=((b[i]+1LL)*b[i]/2LL);//n个等差数列求和 } printf("%lld ",ans); } }
归并排序：
#include<stdio.h> #include<iostream> #include<math.h> #include<string.h> #include<set> #include<map> #include<list> #include<math.h> #include<queue> #include<algorithm> using namespace std; typedef long long LL; #define INF 99999999 #define me(a,x) memset(a,x,sizeof(a)) int mon1[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; LL getval() { LL ret(0); char c; while((c=getchar())==' '||c==' '||c==' '); ret=c-'0'; while((c=getchar())!=' '&&c!=' '&&c!=' ') ret=ret*10+c-'0'; return ret; } void out(int a) { if(a>9) out(a/10); putchar(a%10+'0'); } #define max_v 100005 struct node { LL v,num; } p[max_v],temp[max_v]; void mer(int s,int m,int t) { int i=s; int j=m+1; int k=s; while(i<=m&&j<=t) { if(p[i].v<=p[j].v) { temp[k++]=p[i++]; temp[k-1].num+=(j-m-1); } else { temp[k++]=p[j++]; temp[k-1].num+=(m-i+1); } } while(i<=m) { temp[k++]=p[i++]; temp[k-1].num+=(j-m-1); } while(j<=t) { temp[k++]=p[j++]; temp[k-1].num+=(m-i+1); } } void cop(int s,int t) { for(int i=s; i<=t; i++) p[i]=temp[i]; } void megsort(int s,int t) { if(s<t) { int m=(s+t)/2; megsort(s,m); megsort(m+1,t); mer(s,m,t); cop(s,t); } } int main() { int n; while(~scanf("%d",&n)) { for(int i=0; i<n; i++) { scanf("%lld",&p[i].v); p[i].num=0; } megsort(0,n-1); LL ans=0; for(int i=0; i<n; i++) { ans+=(p[i].num+1)*p[i].num/2LL; } printf("%lld ",ans); } return 0; }
线段树+离散化
#include<stdio.h> #include<iostream> #include<math.h> #include<string.h> #include<set> #include<map> #include<list> #include<math.h> #include<queue> #include<algorithm> using namespace std; typedef long long LL; #define INF 99999999 #define me(a,x) memset(a,x,sizeof(a)) int mon1[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31}; int mon2[13]= {0,31,29,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]= {{0,1},{0,-1},{1,0},{-1,0}}; LL getval() { LL ret(0); char c; while((c=getchar())==' '||c==' '||c==' '); ret=c-'0'; while((c=getchar())!=' '&&c!=' '&&c!=' ') ret=ret*10+c-'0'; return ret; } void out(int a) { if(a>9) out(a/10); putchar(a%10+'0'); } #define max_v 1000005 struct node { LL v,pos; }p[max_v]; LL b[max_v]; LL ans; struct node1 { LL l,r; int w; int f; } tr[max_v*4]; void build(LL k,LL ll,LL rr) { tr[k].l=ll,tr[k].r=rr; if(tr[k].l==tr[k].r) { tr[k].w=0; tr[k].f=0; return ; } LL m=(ll+rr)/2; build(k*2,ll,m); build(k*2+1,m+1,rr); tr[k].w=tr[k*2].w+tr[k*2+1].w; tr[k].f=0; } void down(LL k) { tr[k*2].f+=tr[k].f; tr[k*2+1].f+=tr[k].f; tr[k*2].w+=tr[k].f*(tr[k*2].r-tr[k*2].l+1); tr[k*2+1].w+=tr[k].f*(tr[k*2+1].r-tr[k*2+1].l+1); tr[k].f=0; } void ask_interval(LL k,LL a,LL b)//区间a b的和 { if(tr[k].l>=a&&tr[k].r<=b) { ans+=tr[k].w; return ; } if(tr[k].f) down(k); LL m=(tr[k].l+tr[k].r)/2; if(a<=m) ask_interval(k*2,a,b); if(b>m) ask_interval(k*2+1,a,b); } void change_point(LL k,LL x,LL y)//第x个数加y { if(tr[k].l==tr[k].r) { tr[k].w+=y; return ; } if(tr[k].f) down(k); LL m=(tr[k].l+tr[k].r)/2; if(x<=m) change_point(k*2,x,y); else change_point(k*2+1,x,y); tr[k].w=tr[k*2].w+tr[k*2+1].w; } bool cmp(node x,node y) { if(x.v!=y.v) return x.v<y.v; else return x.pos<y.pos; } int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) { cin>>p[i].v; p[i].pos=i; } sort(p+1,p+1+n,cmp);//离散化 me(b,0); build(1,0,n); for(int i=1;i<=n;i++) { change_point(1,p[i].pos,1); ans=0; ask_interval(1,1,p[i].pos); b[i]+=i-ans; } build(1,0,n); for(int i=n;i>=1;i--) { change_point(1,p[i].pos,1); ans=0; ask_interval(1,0,p[i].pos-1); b[i]+=ans; } ans=0; for(int i=1;i<=n;i++) { ans+=(b[i]+1LL)*b[i]/2LL; } cout<<ans<<endl; } return 0; }