计算数组的小和

链接：https://www.nowcoder.com/questionTerminal/edfe05a1d45c4ea89101d936cac32469 来源：牛客网

数组小和的定义如下：

例如，数组s = [1, 3, 5, 2, 4, 6]，在s[0]的左边小于或等于s[0]的数的和为0；在s[1]的左边小于或等于s[1]的数的和为1；在s[2]的左边小于或等于s[2]的数的和为1+3=4；在s[3]的左边小于或等于s[3]的数的和为1；

在s[4]的左边小于或等于s[4]的数的和为1+3+2=6；在s[5]的左边小于或等于s[5]的数的和为1+3+5+2+4=15。所以s的小和为0+1+4+1+6+15=27

给定一个数组s，实现函数返回s的小和

[要求]

时间复杂度为O(nlogn)，空间复杂度为O(n)

输入描述:

第一行有一个整数N。表示数组长度 接下来一行N个整数表示数组内的数

输出描述:

一个整数表示答案

示例1

输入

6 1 3 5 2 4 6

输出

27

备注:

1⩽N⩽10^5 −100⩽arri⩽100

解：本质上是归并排序问题，只是在每次排序之前先检查出左边比右边小的数据。

#include<bits/stdc++.h> using namespace std; long mergeSort(int a[],int n); long sortProcess(int a[],int L,int R); long merge(int a[],int L,int mid,int R); int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; cout<<mergeSort(a,n)<<endl; return 0; } long mergeSort(int a[],int n) { if(a==NULL||n<2) return 0; return sortProcess(a,0,n-1); } long sortProcess(int *a,int L,int R) { if(L>=R) return 0; int mid=L+((R-L)>>1);//相当于(L+R)/2,可有效避免溢出 return sortProcess(a,L,mid)+sortProcess(a,mid+1,R)+merge(a,L,mid,R); } long merge(int *a,int L,int mid,int R) { int help[R-L+1];//保存每次merge后的数组 memset(help, 0, sizeof(help)); int i=0; int p1=L; int p2=mid+1; long rul=0; while(p1<=mid&&p2<=R) { //设任意p2<m<R,当a[p1]<=a[p2]时，a[p1]<a[m]也显然成立，m的数量为 R-p2+1 rul+=a[p1]<=a[p2]?(R-p2+1)*a[p1]:0; help[i++]=a[p1]<=a[p2]?a[p1++]:a[p2++];//每次选择小的数字存入数组 } //左右两边的数量不是每次都相等，将剩下的元素也添加到help数组中 while(p1<=mid) { help[i++]=a[p1++]; } while(p2<=R) { help[i++]=a[p2++]; } for(i=0;i<R-L+1;i++) a[L+i]=help[i]; return rul; }