数组单调和

[编程题]数组单调和

热度指数：13365 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。

给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。

测试样例：

[1,3,5,2,4,6],6

返回：27

算法知识视频讲解

烟花一树终化尘

发表于 2022-04-07 23:50:51

问题转化：求单调和（小和）就是统计该元素前有多少小于等于该数的元素之和。问题和归并两个有序数组求小于等于该数的元素之和一样。所以现在的问题变为统计子问题中单调和。 // 当出现nums[i]<=nums[j]时，统计所有前半段区间内比nums[j]小的数 // 展开全文

tru-th

发表于 2022-07-20 14:45:12

使用小数和的计算原理，用到了二分法。如图所示，使用二分查找的思想，先将p(0,6)（即process(0,6)）压入栈中，然后计算p(0,3)，不断向下压栈，直到left和right相等时返回0，然后进行merge操作，指针p1指向left，p2指向mid+1，两者进行比较，如果p1的值，小于等于p 展开全文