找出不能组成的最小和

Question

给定从 1 到 N 的正整数，其中 N 可以达到 10^9。这些给定整数中缺少 K 个整数。 K 最多可以有 10^5 个元素。我需要以有效的方式找到剩余的 N-K 个元素无法形成的最小和。

示例；假设我们有 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

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

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

我们可以使用类似于埃拉托色尼筛法的方法来寻找素数。相同的想法，但出于不同的目的使用不同的规则。

存储从0到所有数字之和的数字，并用0划掉。
然后取号，一次一个，不放回。
当我们取数字 Y 时，然后划掉每个 Y 加上一些先前划掉的数字。
当我们对剩余的每个数字都这样做后，最小的未划掉的数字就是我们的答案。

不过，它的space要求很高。有没有更好更快的方法来做到这一点？

Answer 1

令 X 为初始化为零的位向量。对于每个数字 Ni，您设置 X = (X | X << Ni) |你。（即你可以制造 Ni 并且你可以增加你之前可以通过 Ni 制造的任何价值）。

这将为您可以设置的每个值设置一个“1”。

运行时间在 N 中是线性的，位向量运算很快。

process 1: X = 00000001
process 2: X = (00000001 | 00000001 << 2) | (00000010) = 00000111
process 4: X = (00000111 | 00000111 << 4) | (00001000) = 01111111

第一个你做不出来的数字是 8。

Answer 2

这是一个时间复杂度为 O(sort(K)) 的算法。

设 1 ≤ x₁ ≤ x₂ ≤ ……≤ x_m 是集合中缺失的 not 整数。对于从 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[=18=的所有和]i，没有其他）。

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

Answer 3

这是我的 O(K lg K) 方法。由于惰性溢出，我没有对其进行太多测试，对此感到抱歉。如果它适合你，我可以解释一下这个想法：

const int MAXK = 100003;

int n, k;
int a[MAXK];

long long sum(long long a, long long b) { // sum of elements from a to b
  return max(0ll, b * (b + 1) / 2 - a * (a - 1) / 2);
}

void answer(long long ans) {
  cout << ans << endl;
  exit(0);
}

int main() 
{
    cin >> n >> k;
  for (int i = 1; i <= k; ++i) {
    cin >> a[i];
  }

  a[0] = 0;
  a[k+1] = n+1;

  sort(a, a+k+2);

  long long ans = 0;
  for (int i = 1; i <= k+1; ++i) {
    // interval of existing numbers [lo, hi]
    int lo = a[i-1] + 1;
    int hi = a[i] - 1;

    if (lo <= hi && lo > ans + 1)
      break;

    ans += sum(lo, hi);
  }

  answer(ans + 1);
}

编辑：好吧，感谢上帝@DavidEisenstat 在他的回答中写了我使用的方法的描述，所以我不必写它。基本上，他所说的练习不是一个一个地添加"existing numbers"，而是同时添加。在此之前，您只需要检查它们中的一些是否破坏了不变量，这可以使用二分查找来完成。希望对你有帮助。

EDIT2：正如@DavidEisenstat 在评论中指出的那样，不需要二进制搜索，因为只有现有数字的每个区间中的第一个数字才能打破不变量。相应地修改了代码。

找出不能组成的最小和

Find minimum sum that cannot be formed

algorithm

minimum