蓝桥杯历届试题-小朋友排队 （C++代码）

#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;
}