小和问题

题目描述

本题要求计算一个特定数组的小和。

所谓“小和”，指的是数组中每个元素左侧所有小于该元素的数值的总和。换句话说，对于数组中的每个数，我们需要找出其左侧所有比它小的数，并将这些数累加起来。这个过程需要对数组中的每个元素都进行一次，然后将所有的累加结果相加，最终得到的就是该数组的小和。

举例说明，给定数组 [1,3,4,2,5]，我们需要进行以下步骤来计算小和：

1. 对于数字1，其左侧没有比它小的数，所以累加和为0。
2. 对于数字3，其左侧只有1比它小，所以累加和为1。
3. 对于数字4，其左侧有1和3比它小，所以累加和为1+3=4。
4. 对于数字2，其左侧只有1比它小，所以累加和为1。
5. 对于数字5，其左侧所有的数（1,3,4,2）都比它小，所以累加和为1+3+4+2=10。

最后，我们将以上所有累加和相加，即0+1+4+1+10=16，所以这个数组 [1,3,4,2,5] 的小和为16。

现在，请编写程序来计算任意给定数组的小和。

输入

输入格式见样例。

输出

输出应为一个整数，表示输入数组的小和。

样例

提示

思路一：使用暴力枚举。两层for循环遍历数组，将每一个和他前面的数字比过去，只要比这个数小就与结果相加实现。

思路二：归并排序解题。在二路归并的过程中，会对数组的左右元素逐一进行比较，小和就可以在Merge的过程中被求解。

提交人

来源/分类