历届试题-小朋友排队

 历届试题 小朋友排队   时间限制：1.0s   内存限制：256.0MB      问题描述 　　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。 既然要交换次数和总和最少，也就是要求每一个人的交换次数最少,所以说求出每一个最少交换次数是关键， 如何求出每一个的最少交换次数：就是对于某一个人来说，一定要与前面比他高和后面比他矮的人交换，所以他的前面比他高的人数+后面比他矮的人数=最少交换次数（由此想到了逆序数问题） 一般逆序数只求他的前面的，这里有针对每一个数分别求他的前面和后面逆序数 clude<cstdio> #include<cstdlib> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int MAX=100010; struct Node { int val; int pos; }node[MAX]; int c1[MAX],c2[MAX],reflect[MAX],n; bool cmp(Node a,Node b) { return a.val<b.val; } int lowbit(int x) { return x&(-x); } void update(int x,int c[]) { while(x<=n) { c[x]++; x+=lowbit(x); } } int getsum(int now,int c[]) { int sum=0; while(now>0) { sum+=c[now]; now-=lowbit(now); } return sum; } int main() { long long ans[MAX],i; long long sum; while(~scanf("%d",&n)&&n) { for(i=1;i<=n;i++) { scanf("%d",&node[i].val); node[i].pos=i; } sum=0; sort(node+1,node+n+1,cmp); memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); memset(ans,0,sizeof(ans)); for(i=1;i<=n;i++) { if(i!=1&&node[i].val==node[i-1].val) reflect[node[i].pos]=reflect[node[i-1].pos];//当出现重复数字时，为了方面后方逆序数的查找，标记为同一位置 else //这样就不会出现把与自己相等的数当成逆序数的情况 reflect[node[i].pos]=i; //reflect[实际位置]=排序后应该在的位置 } for(i=1;i<=n;i++) { update(reflect[i],c1); ans[i]+=i-getsum(reflect[i],c1); } for(i=n;i>=1;i--) { update(reflect[i],c2); ans[i]+=getsum(reflect[i]-1,c2);//getsum()只计算当前数之前的逆序数，不再算上自己和与自己相同的， //因为标记与自己相同而又出现在自己前面的很麻烦 } for(i=1;i<=n;i++) { sum+=(1+ans[i])*ans[i]/2; } cout << sum << endl; } return 0; } 还有两个问题，1.ans[]定义成int型没有通过，改成long long就过了 2.正序判断逆序数如果不考虑多个相同的数公用同一位置会不会出错