找出无法形成的最小金额

Question

给出从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. 当我们为剩下的每个数字完成此操作时,最小的未交叉数字是我们的答案.

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

Answer 1

这是一个 O(sort(K)) 时间算法。

令 1 ≤ x ₁ ≤ x ₂ ≤ … ≤ x _m为集合中不缺失的整数。对于从 0 到 m 的所有 i，令 y _i = x ₁ + x ₂ + … + x _i为前 i 项的部分和。如果存在，则令 j 为满足 y _j + 1 < x _j+1的最小索引；否则，令 j = m。通过归纳法可以证明，不能得到的最小和是 y _j + 1（假设是，对于从 0 到 j 的所有 i，数字 x ₁ , x ₂ , …, x _i可以使所有从 0 到 y _{i 的}总和，没有其他）。

为了处理指定缺失数字的事实，有一种优化可以在恒定时间内处理多个连续数字。我会把它留作练习。