计算数组的小和

[编程题]计算数组的小和

热度指数：2432 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

数组小和的定义如下：

$\sum_{i=1}^{n} f_i \$ (其中 $f _i\$ 的定义是第 i 个数的左侧小于等于 $s_i\$ 的个数)

例如，数组 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 的小和

数据范围： $0 < n \le 10^{5} \$ ， $|s_i| \le 100 \$

示例1

输入

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

输出

示例2

输入

[1]

输出

算法知识视频讲解

NiimiSora

发表于 2022-08-30 20:20:10

题目分析根据左神讲的smallSum先可以写出暴力方法：数组 s = [1, 3, 5, 2, 4, 6] ，在 s[0] 的左边小于或等于 s[0] 的数的和为 0 ；在 s[1] 的左边小于或等于 s[1] 的数的和为 1 ；在 s[2] 的左边小于或等于 s[2] 的数的和为 1+3= 展开全文

17c89

发表于 2024-08-30 19:30:21

import java.util.*; /** * NC349 计算数组的小和 * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文

雪号鸟

发表于 2024-03-25 16:27:35

#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector 展开全文

17c89

发表于 2024-10-14 12:24:49

import java.util.*; /** * NC349 计算数组的小和 * @author d3y1 */ public class Solution { // 树状数组t private int[] t; // 线段树 private int[] 展开全文

姐姐的遮阳伞

发表于 2022-04-08 19:02:23

import java.util.*; public class Solution { public long ans = 0l; /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param 展开全文

牛客942109102号

发表于 2022-04-26 19:51:22

利用归并排序可以记录比较大小的过程，且无重复不遗漏的特点，来计算小和。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return long长整展开全文