找出绳子的最小长度
Find the minimum length of rope
我有以下编程问题：
给定一个整数长度数组作为输入，每个元素表示所需绳索的长度，求出原始绳索的最小长度，因为在每一步中，您只能将绳索长度减半每根绳子的必须是一个整数。如果不存在这样的绳索，则输出-1。
关于将长度为 x 的绳子“减半”的附加信息：
- 如果 x 可以被 2 整除，那么得到的两条绳子的长度将是 x/2
- 否则，生成的两条绳子的长度为地板（x/2）和天花板（x/2）
例如，如果我需要 [3, 5, 2]，那么我需要的最小尺寸绳索是 10，因为“10”可以拆分为 2 个“5”，剩下的“5”之一可以是拆分为“3”和“2”。然后，我最终会得到我需要的 [3, 5, 2]。也允许以不需要的过多绳索结束。
我获得了一个函数，可以确定特定长度的绳索是否可以分成所需的长度。
我最初想在搜索 space [所需绳索的最大长度，___] 中进行某种二进制搜索，但我不确定上限应该是多少是。另外，我意识到这不一定有效，因为更长的绳索不一定能保证绳索可以分成所需的长度。
现在，我唯一的解决方案是线性搜索，但这似乎太慢了，而且我不确定会导致没有有效绳索的条件。
非常感谢任何指导！
考虑任何所需的段长度 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), ..., I(m_i, 64)。我们知道解绳的长度x一定包含在每个n组X(m_1), X(m_2), ..., X(m_n)中。因此，我们缩小了 space 对所有 X(m_i).
交集的搜索范围。
您可以通过首先生成 64 * n 间隔 I(m_i, k) 来高效地遍历搜索 space 中的所有值，每个间隔由您喜欢的编程语言中的一对整数表示（小心溢出！）。然后使用快速整数排序器按它们的第一个组件（即按它们的左间隔边界）对这些对进行排序，例如基数排序。最后，迭代搜索 space 只需要仔细 left-to-right 扫描排序的间隔，始终检查所需的交集（我在这里故意省略了一些技术细节）。
以最短绳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], ...
如您所见，搜索 space 明显变小了，因此解实际上是搜索的第二小元素 space!
希望对您有所帮助 ;)
我有以下编程问题：
给定一个整数长度数组作为输入，每个元素表示所需绳索的长度，求出原始绳索的最小长度，因为在每一步中，您只能将绳索长度减半每根绳子的必须是一个整数。如果不存在这样的绳索，则输出-1。
关于将长度为 x 的绳子“减半”的附加信息：
- 如果 x 可以被 2 整除，那么得到的两条绳子的长度将是 x/2
- 否则，生成的两条绳子的长度为地板（x/2）和天花板（x/2）
例如，如果我需要 [3, 5, 2]，那么我需要的最小尺寸绳索是 10，因为“10”可以拆分为 2 个“5”，剩下的“5”之一可以是拆分为“3”和“2”。然后，我最终会得到我需要的 [3, 5, 2]。也允许以不需要的过多绳索结束。
我获得了一个函数，可以确定特定长度的绳索是否可以分成所需的长度。
我最初想在搜索 space [所需绳索的最大长度，___] 中进行某种二进制搜索，但我不确定上限应该是多少是。另外，我意识到这不一定有效，因为更长的绳索不一定能保证绳索可以分成所需的长度。
现在，我唯一的解决方案是线性搜索，但这似乎太慢了，而且我不确定会导致没有有效绳索的条件。
非常感谢任何指导！
考虑任何所需的段长度 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), ..., I(m_i, 64)。我们知道解绳的长度x一定包含在每个n组X(m_1), X(m_2), ..., X(m_n)中。因此，我们缩小了 space 对所有 X(m_i).
您可以通过首先生成 64 * n 间隔 I(m_i, k) 来高效地遍历搜索 space 中的所有值，每个间隔由您喜欢的编程语言中的一对整数表示（小心溢出！）。然后使用快速整数排序器按它们的第一个组件（即按它们的左间隔边界）对这些对进行排序，例如基数排序。最后，迭代搜索 space 只需要仔细 left-to-right 扫描排序的间隔，始终检查所需的交集（我在这里故意省略了一些技术细节）。
以最短绳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], ...
如您所见，搜索 space 明显变小了，因此解实际上是搜索的第二小元素 space!
希望对您有所帮助 ;)