#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语言代码)浏览:785 |
分糖果 (C++代码)浏览:855 |
点我有惊喜!你懂得!浏览:1402 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:617 |
C语言考试练习题_保留字母 (C语言代码)浏览:561 |
九宫重排 (C++代码)浏览:1326 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1022 |
printf基础练习2 (C语言代码)浏览:941 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:597 |
printf基础练习2 (C语言代码)浏览:644 |