algorithm - 找出绳子的最小长度

Question

我有以下编程问题:

给定一个整数长度数组作为输入，每个元素表示所需绳索的长度，求出原始绳索的最小长度，前提是在每一步中，你只能得到绳索长度的一半和每根绳索长度的一半rope 必须是整数。如果不存在这样的绳索，则输出 -1。

关于将长度为 x 的绳子“减半”的附加信息:

• 如果 x 可以被 2 整除，那么得到的两根绳子的长度为 x/2
• 否则，生成的两条绳索的长度为 floor(x/2) 和 ceiling(x/2)

例如，如果我需要 [3, 5, 2]，那么我需要的最小尺寸绳索是 10，因为“10”可以拆分为 2 个“5”，而剩余的“5”之一可以拆分为'3' 和 '2'。然后，我最终会得到我需要的 [3, 5, 2]。也允许以不需要的过多绳索结束。

我得到了一个函数，可以确定特定长度的绳索是否可以分成所需的长度。

我最初想在搜索空间中进行某种二进制搜索 [需要的最大绳索长度，___]，但我不确定上限应该是多少。此外，我意识到这不一定有效，因为较长的绳索不一定能保证绳索可以分成所需的长度。

现在，我唯一的解决方案是线性搜索，但这似乎太慢了，而且我不确定会导致没有有效绳索的条件。

非常感谢任何指导!

Answer 1

考虑任何所需的段长度 m，并假设我们希望通过恰好将绳子对分 k 次来获得该段。那么我们考虑的最短绳索的长度为 (2^k)*m - 2^k + 1。如果我们将这条绳子切成两半 k 次，每一步都丢弃较短的一半，那么我们最终会得到一段长度为 m 的绳子。我们考虑的最长绳索的长度为 (2^k)*m + 2^k - 1。如果我们将这条绳子切成两半 k 次，每一步都丢弃较长的一半，那么我们最终也会得到一段长度 m。

对于我们的长度 m 段，我们因此只需要考虑长度在 [(2^k)*m - 2^k + 1, (2^ k)*m + 2^k - 1] 对于一些正整数 k。在合理假设最终绳索长度可以用 64 位无符号整数表示的情况下，k 最多为 64。因此，使用我们上面的区间表示法，只有 64 个区间包含所有可能的绳索可用于获取长度 m 段的长度。

现在有趣的部分来了:假设有 n 段所需的长度 m_1, m_2, ..., m_n。对于任何段 m_i，我们正式定义第 k 个候选区间为:

I(m_i, k) = [(2^k)*m_i - 2^k + 1, (2^k)*m_i + 2^k - 1]

对于任何段 m_i，让 X(m_i) 表示 64 个候选区间的并集 I(m_i, 1), I(m_i, 2 ), ..., 我(m_i, 64)。我们知道解绳的长度x一定包含在每个n集合X(m_1), X(m_2), ..., X(m_n)。因此，我们将搜索空间缩小到所有 X(m_i) 的交集。

您可以通过首先生成 64 * n 区间 I(m_i, k) 来高效地迭代搜索空间中的所有值，每个区间由一对整数表示用你最喜欢的编程语言(小心溢出!)。然后使用快速整数排序器按它们的第一个组件(即按它们的左间隔边界)对这些对进行排序，例如基数排序。最后，遍历搜索空间只需要仔细地从左到右扫描排序的间隔，始终检查所需的交集(我在这里有意省略了一些技术细节)。

以最短绳索57所需的段[7,7,8,14]为例:

I(7, 1) = [13, 15]
I(7, 2) = [25, 31]
I(7, 3) = [49, 63]
I(7, 4) = [97, 127]
...

I(8, 1) = [15, 17]
I(8, 2) = [29, 35]
I(8, 3) = [57, 71]
I(8, 4) = [113, 143]
...

I(14, 1) = [27, 29]
I(14, 2) = [53, 59]
I(14, 3) = [105, 119]
...

Search Space: [29,29], [57,59], [113,119], ...

如您所见，搜索空间变得非常小，以至于解决方案实际上是搜索空间中第二小的元素!

希望这有帮助；)