首页 > 试题广场 >

计算数组的小和

[编程题]计算数组的小和
  • 热度指数：11658 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
数组小和的定义如下：
(其中 的定义是第 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 的小和

数据范围： ，

输入描述:
第一行有一个整数N。表示数组长度
接下来一行N个整数表示数组内的数


输出描述:
一个整数表示答案
示例1

输入

6
1 3 5 2 4 6

输出

27
示例2

输入

1
1

输出

0

备注:

算法知识视频讲解
开通博客
头像 总之就是非常可爱
发表于 2022-02-11 10:48:39
//小和问题可以转化成求某个数右边大于等于他的数的个数乘当前这个数 //而求某个数右边有多少个大于等于他的数可以使用使用归并排序解决 //在归并排序中有一个过程是合并两个已经有序的数组，在这个过程中就可以实现计算某个数右边有多少个大于等于他的数 //这题有个巨坑就是不能用int类型 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 愿每个人都能被温柔以待
发表于 2021-08-08 20:11:41
借助 「归并排序」的思路。smallSum([1,3,4,2,5])实际就等于smallSum([1,3,4])+smallSum([2,5]) + smallSum_Merge。smallSum_Merge等于左半段数组中比右半段数组小的元素。在归并排序的merge过程中计算这个smallSum_ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 帅过地球一半的男人
发表于 2022-09-18 21:30:29
反向思路：从左往右，有多少个比当前元素a大的数，就产生多少个a的小和。 以1, 3, 5, 2, 4, 6为例，比1大的有5个元素，所以产生5个1小和，比3大的有3个，所以产生3个3的小和，即9，以此类推，5产生5，2产生4，4产生4，6产生0，所以数组小和为5+9+5+4+4+0=27 具 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 吴清忠201808271120204
发表于 2024-04-08 14:40:53
// 按照左神的思路写的 // https://www.bilibili.com/video/BV1L14y1B7ef/?spm_id_from=trigger_reload&vd_source=8ea6dc6c02215b66383cf6ab9791e3b4 #include <c 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 心折风
发表于 2024-03-11 00:42:08
#include<iostream> using namespace std; const int MAXN = 100001; int arr[MAXN]; int help[MAXN]; int n; // 返回跨左右产生的小和累加和，左侧有序、右侧有序，让左右两侧整体有序 // 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 GXCO
发表于 2024-11-27 01:10:59
// 测试链接 https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469 #include <iostream> using namespace std; using ll = long long; // 为 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 快支棱起来的椰子很愤怒
发表于 2022-01-12 15:07:28
n = int(input()) nums = list(map(int, input().split())) def merge_sort(left, right): if left >= right: return 0 m = (left + right) 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 心折风
发表于 2024-08-07 16:44:57
#include <iostream> #include <vector> using namespace std; long long merge(vector<int>& arr,vector<int>& help,int l, i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 脆脆脆脆脆脆鲨
发表于 2023-05-03 15:12:00
package main import ( "fmt" ) func main() { var arr []int var n, tmp int fmt.Scan(&n) for i := 0; i < n; i++ { fmt.Scan( 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 寄居的过客
发表于 2022-09-03 20:45:15
写了两版 都能AC 只不过 第一版像吃了屎一样难看 这题关键是 只要在左边数组 找到一个小的 则右数组都会小直接乘于右边数组剩下的个数即可 第一版 想法是 只要找到右边大的时候 此时在 左边数组之前 arr[l] 的都是小的 遍历把它们都加上 想法没有第二版精妙 impo 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

二分 排序
上传者：小小
难度：
39条回答 9176浏览

热门推荐

通过挑战的用户

查看代码

相关试题

计算数组的小和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号