在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和.求一个数组的小和.
4左边比4小的数:13
5左边比5小的数:1342
所以小和为1+1+3+1+1+3+4+2=16
如果直接用两层for循环扫,时间复杂度是$O(n^2)$,但是可以通过归并排序的方法将时间复杂度降到O(nlogn)
分完以后开始治,归并排序的治就是merge的过程,首先对1和3进行merge,在此过程中产生一个小和1;然后将1,3和4进行merge,在此过程中产生小和1,3;然后2和5进行merge,产生小和2;最后将1,3,4和2,5进行一次merge,1比2小,所以一共产生n个1的小和,这个n就是当前右边的数的个数,因为右边有两个数2和5,所以产生2个1的小和,然后将1填入辅助数组,继续比较3和2,2比3小,但是2是右边的数,所以不算小和,然后比较3和5,3比5小,所以产生n个3的小和,因为右侧只有一个数,所以就只产生1个3的小和,同样的,产生1个4的小和
这道题换个角度来想,题目要求的是每个数左边有哪些数比自己小,其实不就是右边有多少个数比自己大,那么产生的小和就是当前值乘以多少个吗?还是以上面的样例举例,1右边有4个比1大的数,所以产生小和1*4;3右边有2个比3大的数,所以产生小和3*2;4右边有一个比4大的数,所以产生小和4*1;2右边没有比2大的数,所以产生小和为2*0;5右边也没有比5大的数,所以产生小和5*0