小编use*_*ser的帖子

给出从1到N的正整数,其中N可以达到10 ^ 9.缺少来自这些给定整数的一些K个整数.K可以是最多10 ^ 5个元素.我需要找到无法通过有效方式从剩余的NK元素中形成的最小总和.

例; 假设我们有N = 5,这意味着我们有{1,2,3,4,5}并且让K = 2而缺少的元素是:{3,5}那么剩下的数组现在是{1,2,4}最小值不能从这些剩余元素形成的总和为8,因为:

1=1
2=2
3=1+2
4=4
5=1+4
6=2+4
7=1+2+4

那么如何找到这个不可归小的最小值呢？

如果我可以通过这种方法存储所有剩余元素,我知道如何找到它:

我们可以使用类似于Eratosthenes筛子的东西,用于寻找素数.同样的想法,但为不同的目的有不同的规则.

1. 将数字从0存储到所有数字的总和,然后交叉0.
2. 然后一次取一个数字,无需更换.
3. 当我们取数字Y时,然后将每个Y加上一些先前交叉的数字交叉.
4. 当我们为剩下的每个数字完成此操作时,最小的未交叉数字是我们的答案.

但是,它的空间要求很高.有没有更好更快的方法呢？