Python中最小化切割所需时间问题

在此问题中，我们给出了一个整数，即给定木棍的长度。我们在问题中的任务是将木棍分成多个部分。木棍的每个部分都具有单位长度。我们必须最小化分割所需的时间。请注意，我们可以切割木棍的任何部分。

让我们看一些例子来理解这个问题。

示例

输入： N = 50

输出 7

输入： N = 65

输出 7

说明

最初，我们有一根长度为 65 单位的木棍。第一次切割将木棍分成 32 单位和 33 单位。然后，第二次切割将第一部分分成三份，每份 16 单位，第二部分 17 单位。然后我们将它分成 7 份，每份 8 单位，第二份 9 单位。然后，我们可以将木棍分成 15 份，每份 4 单位，一份 5 单位。然后，我们可以将木棍分成 31 份，每份 2 单位，一份 3 单位。然后，我们可以将木棍分成 65 份，每份 1 单位，一份 2 单位。然后，我们可以将木棍分成 65 份，每份 1 单位。

方法 - 1

为了解决这个问题，我们必须专注于在每次切割后最大化木棍的切片数。我们一次只能切割木棍一次。因此，我们的主要目标将是最大化每次切割后的部分数量。我们的策略是进行切割，以便在每次切割中获得尽可能长的长度。

图解

N = 100

第一次切割后

50 + 50

第二次切割后：25 + 25 + 25 + 25

第三次切割后：12 + 13 + 12 + 13 + 12 + 13 + 12 + 13

第四次切割后：6 + 6 + 6 + 7 + 6 + 6 + 6 + 7 + 6 + 6 + 6 + 7 + 6 + 6 + 6 + 7

第五次切割后：3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4

第六次切割后：1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1, 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

第七次切割后：100 份，每份 1 单位

因此，将 N 长度的木棍分割成 1 单位长度的最小时间是 ceil(log2N)。

以上方法的实现如下：

代码

输出

7

时间复杂度： 我们没有使用任何循环来解决这个问题，因此该方法的时​​间复杂度是常数，即 O (1)。

辅助空间： 我们没有使用任何额外的空间，因此空间复杂度是常数，即 O (1)。