#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 人评分
C语言训练-阶乘和数* (C语言代码)-------- 呆板写法浏览:1362 |
C语言训练-大、小写问题 (C语言代码)浏览:732 |
WU-C语言程序设计教程(第三版)课后习题11.12 (C++代码)(想学链表的小伙伴可以看看)浏览:904 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:690 |
1011题解浏览:765 |
愚蠢的摄影师 (C++代码)浏览:938 |
C二级辅导-等差数列 (C语言代码)浏览:695 |
Quadratic Equation (C语言代码)浏览:988 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:673 |
C二级辅导-分段函数 (C语言代码)浏览:759 |