计算数组的小和

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

热度指数：10136 时间限制：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

输出

备注:

算法知识视频讲解

Python

牛客583725131号

# python3 solution
def min_sum(array, l, r):
	if l + 1 == r:
		return 0

	l_min_sum = min_sum(array, l, (l + r) >> 1)
	r_min_sum = min_sum(array, (l + r) >> 1, r)
	extra = merge(array, l, r)
	
	return l_min_sum + r_min_sum + extra


def merge(array, l, r):
	"""Merge sort."""
	res = 0
	# sorted array[l: r]
	temp = [0 for _ in range(r - l)]
	m = (l + r) >> 1
	i, j = l, m
	k = 0
	while i < m and j < r:
		if array[i] <= array[j]:
			res += array[i] * (r - j)
			temp[k] = array[i]
			i += 1
		else:
			temp[k] = array[j]
			j += 1
		k += 1

	while i < m:
		temp[k] = array[i]
		i += 1
		k += 1

	while j < r:
		temp[k] = array[j]
		j += 1
		k += 1

	array[l: r] = temp

	return res

n = int(input())
x = [int(y) for y in input().split(' ')]
print(min_sum(x, 0, n))

编辑于 2021-05-01 23:19:15 回复(0)