#include<cstdio> #define maxn 100010 struct data { int num,cnt; }A[maxn],temp[maxn]; int n; //long long ans; long long ANS[100]; void merge(int L1,int R1,int L2,int R2) { int k=0,i=L1,j=L2; while(i<=R1 && j<=R2) { if(A[i].num<=A[j].num)//如果A[i].num<A[j].num,则A[L2,j-1]的元素小于A[i],如果相等,则先存储上数组的元素,这个时候下数组的A[L2,j-1]仍然都满足小于A[i].num { A[i].cnt+=j-L2; temp[k++]=A[i++]; } else if(A[i].num>A[j].num)//A[i,R1]都大于A[j] { A[j].cnt+=R1-i+1; temp[k++]=A[j++]; } } //剩下上数组,那么剩下的元素都要移动下数组的元素个数 while(i<=R1) { A[i].cnt+=R2-L2+1; temp[k++]=A[i++]; } while(j<=R2) temp[k++]=A[j++]; //剩下下数组,就不需要移动 for(i=0;i<k;i++) A[L1+i]=temp[i]; } void mergeSort(int L,int R) { if(L<R) { int mid = (L+R)/2; mergeSort(L,mid); mergeSort(mid+1,R); merge(L,mid,mid+1,R); } } int main(void) { //FILE *in = fopen("input10.txt","r"); //fscanf(in,"%d",&n); //for(int i=0;i<n;i++) fscanf(in,"%d",&(A[i].num)); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&(A[i].num)); mergeSort(0,n-1); for(int i=0;i<n;i++) { long long s = A[i].cnt; //ans+=s*(s+1)/2; ANS[1]+=s*(s+1)/2; int length=1; while(ANS[length]/10!=0) { ANS[length+1]+=ANS[length]/10; ANS[length]%=10; length++; } if(ANS[0]<length) ANS[0]=length; } //printf("%lld",ans); for(int i=ANS[0];i>=1;i--) printf("%d",ANS[i]); //printf("\n"); return 0; }
0.0分
4 人评分
2005年春浙江省计算机等级考试二级C 编程题(3),复杂度最低的方法没有之一!!!!!浏览:850 |
C语言训练-大、小写问题 (C语言代码)浏览:2414 |
九宫重排 (C++代码)浏览:2191 |
C语言训练-排序问题<1> (C语言代码)浏览:632 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1437 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:603 |
C语言程序设计教程(第三版)课后习题8.7 (C语言代码)浏览:604 |
1113题解浏览:818 |
蚂蚁感冒 (C语言代码)浏览:804 |
震宇大神的杀毒软件 (C语言代码)浏览:1156 |