通过总和了解多重集中的重复

Question

我得到了多重集的大小 N 及其总和 S。集合的元素应该是连续的，例如多重集 K 有 6 (N=6) 个元素 {1,1,2,2,2,3}，所以 S=11（多重集总是包含第一个 N 重复自然数).

我怎样才能知道要进行的总更改，以便不会有重复并且集合变得连续？

对于上面的示例，多重集 K 需要 3 处更改。因此，最后集合 K 将变为 {1,2,3,4,5,6}。

我所做的是，我找出实际总和（即 n*(n+1)/2）并减去给定的总和。让它成为 T。

然后，T=ceil(T/n)，则答案变为2*T，它适用于大多数情况。

但是，我想我遗漏了一些案例。是否存在某种算法可以知道要更改多少个元素？

我只给出了多重集的大小和总和。

Answer 1

正如您已经注意到的，对于给定的 N，总和应该是 S' = N * (N-1) / 2。给你一些值 S.

显然，如果 S' = S 答案是 0。

如果S'- S <= N - 1，则需要最少更改的多重集是

{1, 2, ..., N-1, X}

其中 X = N - (S' - S)，在 [1, N-1] 范围内。换句话说，X 弥补了所需和实际多重集之间的总和差异。你的答案是 1.

如果差异大于N-1，那么N-1也不能在多重集中。如果 S'- S <= (N - 1) + (N - 2)，需要最少更改的多重集是

{1, 2, ..., N-2, 1, X}

其中 X = N + (N - 1) - (S'- S)，在 [1, N-2] 范围内。你的答案是 2.

一般化，你会得到一个 table 像：

   S' - S    |  answer
-----------------------
[   0,    0] |     0
[   1,  N-1] |     1
[   N, 2N-3] |     2
[2N-2, 3N-6] |     3

等等。您可以根据 N 和 S 找到一个公式来得到答案，但使用简单的循环似乎更容易。我会把实现留给你。

Know repetitions in multiset by its sum