C++ 中确定是否可以通过将木棍段分成两半来得到数组

在基于计算机的问题解决中，有些问题只能通过处理基本事物来解决，比如棍子或相似的物品组。有一个这样的问题：给定一系列基本事物（一个数组），我们是否可以通过分割一根（我们开始时拥有的）棍子来得到正好那些碎片。我们可以根据需要多次折断棍子，但每次折断时，都必须将其分成两半。

这项任务之所以有趣，是因为它的设置与我们在现实生活以及在其他计算机程序中遇到的情况相似，在这些情况下，我们必须一遍又一遍地重复某些步骤，直到某些事情结束。

在处理这项任务时，我们首先必须理解按照规则折断棍子意味着什么，这与我们通常的做法不同。如果一根棍子在每次折断时都被分成两半，那么它可以取的不同长度是什么？

• 如果我们说原始棍子的长度是 L，那么 L/2, L/4, L/8，依此类推，直到长度变得非常小，这些是通过以这种方式折断棍子唯一可能获得的长度。
• 例如，可以将长度为八的棍子分成两半，因为 8/2=4。根据我们已经知道的，长度 8 和 4 是允许的。稍后，如果我们把长度为四的棍子之一分成两半，得到的长度是 4、2，以及 8/4=2。
• 提到的最后一个长度 2，是在处理任何正整数长度的棍子时可以获得的最短可能长度。

理解问题陈述

形式上，问题陈述如下：

我们得到一个整数 L，表示初始杆的长度。还给出一个数组 array[]，其中包含我们希望切割的各种段的长度。我们的工作是指定是否可以通过连续地将杆分成两半来生成所有这些段的长度。唯一重要的条件是，在每次操作中，杆必须被分成相等的两半。这意味着我们不能在任意位置进行切割。为了理解这个问题，请考虑一个例子，L=16 且 arr={8,4,2,2}。这里，杆开始时是一个长度为 16 的段。第一次有效的折断显然是将其分成两个长度都为八的段。之后，我们可以取其中一个 8，将其分成两个 4，然后用一个 4，我们可以得到两个 2，从而形成整个数组。这种情况返回 YES，因为我们可以通过有效的对半分操作获得所有碎片。在这种情况下，并非所有情况都如此简单。取 L=16 且 arr={9,4,2,1}。段 9 无法获得，因为切割 16 只得到长度为 8、4、2 和 1 的段，它们会不断地将自身分成两半。这意味着 9 永远不会从任何此类操作中出现。因此，答案是 NO。此外，它还提供了一个非常重要的观察结果：所有数字都必须属于 2 的幂，因为使用长度为 L 的杆只能得到 2 的幂。

为了正式确定可行性条件的条款，我们必须检查以下几点：

杆的长度 L 必须足以覆盖 arr[] 中的所有元素。如果 arr[] 的总和超过 L，则不可能获得所有段。arr[] 中的每个数字都必须是 2 的幂。任何不是 2 的幂的数字都可能无法通过有效的对半分操作形成。 breakdown 过程不需要不同顺序的自然对半分。这意味着我们可以决定折断哪一半，但我们不能强制进行不符合自然对半分规律（如 2 的幂）的分割。

方法

为了检查我们是否可以通过将杆分成两半来形成所需的 数组，我们将采用一种朴素但有效的方法。我们将首先检查 arr[] 中的所有段是否是 2 的幂。由于杆只能分成两半，任何不是 2 的幂的段都不可能形成，因此会立即返回 NO。可以通过按位运算 x & (x - 1) == 0 来有效地检查一个数是否是 2 的幂。

之后，只需要模拟折断过程。为此，我们可以使用带有最大堆的优先队列，并始终优先折断最大的那个。我们从长度为 L 的杆开始，并不断折断可用长度最大的那个。每当我们分割一个部分时，我们再次将两个部分入队。如果我们能够从分段中存在的元素中任意次数地重建原始列表，则输出 YES。如果不能，则输出 NO。

或者，另一个人可以使用多重集来跟踪任何时候可用的段。他们可以模拟这个过程，即从 {L} 开始分成段（不一定是不同的），并检查是否可以从其中选择一个最长的段，然后将其折断，从而将剩余的碎片用于表示数组中的所有元素。

如果我们按非递增顺序对 arr[] 进行排序，它将允许我们简化检查在特定点折断杆是否会得到所有必需碎片的过程。我们只需要看看是否有可能从较大的碎片中选择所有其他必需的碎片。

代码实现

输出

YES, the given array can be obtained by breaking the rod.
NO, it is not possible to obtain the given array by breaking the rod.   

代码解释

• 检查 arr[] 中的每个数字是否是 2 的幂。如果不是，则返回 NO。
• 将 arr[] 按降序排序，以首先处理较大的需求。
• 使用最大堆（优先队列）始终处理最大的可用段。
• 不断折断最大的段，直到我们满足所有需求，或者无法在不违反一项需求的情况下折断段。
• 我们使用哈希映射来跟踪每个需求还需要满足多少次。它有助于我们贪婪地合并小段，而不会超出任何需求的所需大小。
• 如果我们在第 i 个索引处满足了所有需求，我们就将该索引推入答案向量，并更新我们对该需求的哈希映射。
• 最后，如果我们满足了所有需求，则打印 YES；否则，打印 NO。

结论

总之，通过将杆分成两半得到给定数组是否可能的问题之所以有趣，是因为它的解决方案依赖于递归和基于优先级的处理。我们可以使用 2 的幂来快速解决一些情况。为了有效地解决这个问题，我们可以使用优先队列（最大堆）来始终选择最大的段进行折断。我们还使用哈希映射来跟踪每个段长度应出现的次数，以便我们知道何时拥有特定长度的所有段。

如果我们按降序对数组进行排序，这将有助于我们以最少的折断次数给出段，从而简化逻辑。该方法的时间复杂度为 O(n log n + n log L)，其中 L 是最大段大小，这确保了即使对于较大的约束，该解决方案也是实用的。这种类型的问题有实际应用，包括使用材料最高效地将事物切割成特定长度，使用二叉树表示奇偶尺寸的事物，以及将计算机内存分成可访问或不可访问的区域。

我们现在得到了一个解决方案，其中每个段都被考虑在内，这是最好的可能答案。如果我们已经制作了所有要求的段，答案就是 YES。如果在过程中出现任何问题（例如，我们制作了某个段的副本过多），答案就是 NO。