我要招人

去企业版

首页 > 试题广场 >

计算数组的小和

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

热度指数：13674 时间限制：C/C++ 2秒，其他语言4秒空间限制：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 \$

输入描述:

第一行有一个整数N。表示数组长度
接下来一行N个整数表示数组内的数

输出描述:

一个整数表示答案

示例1

输入

6
1 3 5 2 4 6

输出

示例2

输入

1
1

输出

备注:

算法知识视频讲解

总之就是非常可爱

发表于 2022-02-11 10:48:39

//小和问题可以转化成求某个数右边大于等于他的数的个数乘当前这个数 //而求某个数右边有多少个大于等于他的数可以使用使用归并排序解决 //在归并排序中有一个过程是合并两个已经有序的数组，在这个过程中就可以实现计算某个数右边有多少个大于等于他的数 //这题有个巨坑就是不能用int类型展开全文

帅过地球一半的男人

发表于 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 具展开全文

愿每个人都能被温柔以待

发表于 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_ 展开全文

牛客396959330号

发表于 2024-12-21 16:14:41

#include <iostream>//O(NlogN) using namespace std; int a[100005],t[100005],n; long long mergesort(int l,int m,int r){ long long ans=0,sum=0; 展开全文

小莫同学xy

发表于 2025-03-04 16:01:58

#include <iostream> #include <cstdio> using namespace std; const int N=1e5+10; int a[N], tmp[N]; long merge(int l, int mid, int r) { 展开全文

吴清忠201808271120204

发表于 2024-04-08 14:40:53

// 按照左神的思路写的 // https://www.bilibili.com/video/BV1L14y1B7ef/?spm_id_from=trigger_reload&vd_source=8ea6dc6c02215b66383cf6ab9791e3b4 #include <c 展开全文

心折风

发表于 2024-03-11 00:42:08

#include<iostream> using namespace std; const int MAXN = 100001; int arr[MAXN]; int help[MAXN]; int n; // 返回跨左右产生的小和累加和，左侧有序、右侧有序，让左右两侧整体有序 // 展开全文

BSYDD

发表于 2025-04-12 00:49:05

package main import "fmt" var ( res int64 ) func main() { res = 0 var ( n int ) fmt.Scan(&n) arr := make([]int, n) for i : 展开全文

huang_w

发表于 2024-12-07 10:44:12

const rl = require("readline").createInterface({ input: process.stdin, }); const iter = rl[Symbol.asyncIterator](); const readline = async 展开全文

快支棱起来的椰子很愤怒

发表于 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) 展开全文

问题信息

二分排序

上传者：小小

难度：

40条回答 79收藏 10309浏览

通过挑战的用户

查看代码

雪芙花

2023-03-11 16:17:49
pein531

2023-03-06 17:09:13
幸运小🐯Of...

2023-03-03 11:31:18
Dcsgo

2023-02-24 13:17:07
nemo123

2023-02-20 21:07:52

计算数组的小和

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题