无法从集合中获得的最小金额

Question

给定一组正整数,其元素不需要是不同的,我需要找到不能从给定集合的任何子集获得的最小非负和.

例如:if S = {1, 1, 3, 7},我们可以得到0as (S' = {}),1as (S' = {1}),2as (S' = {1, 1}),3as (S' = {3}),4as (S' = {1, 3}),5as (S' = {1, 1, 3}),但是我们无法得到6.

现在我们给出一个array A由N正整数组成的.它们是M查询,每个查询由两个整数组成,Li并Ri描述我的查询:我们需要找到这个不能从数组中获得的Sum elements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]}.

我知道通过蛮力方法在O(2 ^ n)中完成它.但是给了1 ? N, M ? 100,000.这不能做.他们做任何有效的方法也是如此.

Answer 1

概念

假设我们有一个数组bool代表到目前为止尚未找到的数字(通过求和).

对于n我们在有序(增加值)子集中遇到的每个数字S,我们执行以下操作:

1. 对于True位置i中的每个现有值numbers,我们设置numbers[i + n]为True
2. 我们设定numbers[n]为True

使用这种筛子,我们将所有找到的数字标记为True,并且当算法结束时迭代遍历数组将找到最小的无法获得的总和.

精致

显然,我们不能有这样的解决方案,因为数组必须是无限的才能适用于所有数字集.

通过做一些观察可以改进这个概念.输入后1, 1, 3,数组变为(按顺序):

^{(数字代表true值)}

可以做一个重要的观察:

• (3)对于每个下一个号码,如果已经找到以前的号码,它将被添加到所有这些号码中.这意味着如果在数字之前没有间隙,则在处理该数字之后将没有间隙.

对于下一个输入,7我们可以断言:

• (4)由于输入集是有序的,所以没有数字小于 7
• (5)如果没有数字7,则6无法获得

我们可以得出结论:

• (6)第一个间隙代表最小的无法获得的数字.

算法

由于(3)和(6),我们实际上并不需要numbers数组,我们只需要一个值max来表示到目前为止找到的最大数.

这样,如果下一个数字n大于max + 1,则会产生间隙,并且max + 1是最小的无法获得的数字.

否则max就变成了max + n.如果我们经历了整个过程S,结果是max + 1.

实际代码(C#,很容易转换为C):

static int Calculate(int[] S)
{
    int max = 0;
    for (int i = 0; i < S.Length; i++)
    {
        if (S[i] <= max + 1)
            max = max + S[i];
        else
            return max + 1;
    }
    return max + 1;
}

应该运行得非常快,因为它显然是线性时间(O(n)).由于应该对函数的输入进行排序,因此使用quicksort将变为O(nlogn).我已经设法M = N = 100000在不到5分钟的时间内在8个核心上获得了结果.

数字上限为10 ^ 9时,可以使用基数排序来近似排序的O(n)时间,但由于需要大量的排序,这仍然会超过2秒.

但是,在排序之前,我们可以使用 1的统计概率来消除子集.在开始时,检查是否存在1,如果不存在,则每个查询的结果为1,因为无法获取.S

从统计上来说,如果我们从10 ^ 9个数字随机抽样10 ^ 5次,我们有99.9%的机会没有获得单个1.

在每次排序之前,检查该子集是否包含1,如果不是,则其结果为1.

通过此修改,代码在我的机器上运行2毫秒.这是http://pastebin.com/rF6VddTx上的代码