leet_891

package
v0.0.0-...-9cc4e77 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 14, 2019 License: MIT Imports: 1 Imported by: 0

README

题解

这实际是一道数学题,首先可以把A数组排序。对于排序后的A[i],如果它的值被计算,要么它是某个子集的最大值,要么是某个子集的最小值。A[i]如果是集合的最大值,这种集合有多少个呢?很显然,可以从A[0..i-1]这i个元素中任选一些:

  • 当从A[0..i-1]中选一个和A[i]组成2个元素的集合,一共有C(i,1)种
  • 当选两个元素和A[i]一起组成3元素集合时,一共有C(i,2)种
  • ...
  • 当把A[0..i-1]全部选上,可以和A[i]组成一个有i+1个元素的集合,有C(i,i)=1种

因此,A[i]作为最大值的集合有∑ C(i,k) (k属于[1,i])种,根据二项式定理,它的值其实就是(2^i)-1。

同理,如果A[i]作为集合的最小值,一共有2^(N-i)-1个这样的集合。

由于题目是求所有集合(最大值-最小值)的和,相当于所有集合的最大值的和 - 所有集合的最小值的和。

所以对于A[i]来说,它个最大值的和贡献了A[i](2^i -1),它给最小值的和贡献了A[i](2^(N-i) -1),枚举所有A[i]即可。

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL