检查物品桶是否可以交错放置

Check if buckets of items can be placed in an interleaved manner

bucket1 = [1,2,3,4]

bucket2 = [5,6]

bucket3 = [7,8,9,10,11]

bucket4 = [12]

需要将它们放在一个排列中,使得排列中的 3 个连续元素应该来自 3 个不同的桶。

eg: 5,7,12,1,6,8,2,9.. 由于bucket2和bucket4元素都用完了,所以不能这样做。

所以概括一下

有 B0 到 Bn 个桶,每个桶都有 C0 到 Cn 个元素,检查是否可以以交错方式排列,使得排列中的 X 个连续元素应该来自 X 个不同的桶。

如果没有桶有超过 floor((x + 2) / 3) 个项目,这是可能的,其中 x 是项目总数。

对于 x=1,2,3 很明显,如果没有桶有超过 1 个项目是可能的。

对于 x > 3,考虑包含最多项目的桶并从其项目开始,以此类推两次,使用不同的桶。必须至少有三个不同的桶来组成 x。现在你已经将 x 减少了 3,并且在接近极限的情况下用完了每个桶中的一个项目。此外最大的桶可以再次使用,所以你几乎可以从头开始 - 通过归纳法问题是可以解决的。

如果任何桶的数量超过 floor((x + 2) / 3),那么即使您可以使用该模式 X 也无法放入序列中? ? X ? ? ……? ? X.