查找清空数组的最小操作数
Find minimum number of operations on to empty an array
我最近在面试中遇到了一个问题，我得到了一条鳄鱼的大小和一个代表池塘中鱼的大小的数组。
鳄鱼可以吃小于它大小的鱼，每次它吃掉那条鱼，它的大小就会随着那条鱼的大小而增加。我们可以对数组执行任意次数的两种类型的操作。
- 从池塘中取出所有鱼
- 向池塘添加任意大小的鱼
给定鳄鱼的初始大小和池塘中的鱼群，我们必须找到最小的编号。此类操作以清空表示池塘的数组。
例如-
鳄鱼的初始大小为 20，鱼的数组为
[10,15,20,30,100]
在这种情况下，鳄鱼吃掉了除 100 以外的所有鱼，它的大小变为 85，因此解决方案之一可能是移除大小为 100 的鱼。因此输出将为 1。
实现上述问题的最佳算法是什么，可以递归求解吗？
所以首先，对数组进行排序。鳄鱼会吃掉每条比他小的鱼。从左边开始，如果鳄鱼能吃到鱼，就增加它的体型。如果没有鱼了，return0。如果没有，做两个变量，一个潜在的结果=无穷大和动作=0。一个可能的答案是删除剩下的鱼。将结果设置为最小值（结果，fish_left + 操作）。然后尝试添加新鱼。你总是希望鳄鱼长得尽可能大，所以插入一条比鳄鱼小 1 的鱼（将它的大小乘以 2 再减 1）。将动作增加一个。让鳄鱼吃掉所有可能的鱼。重复直到所有的鱼都被吃掉，然后 return 结果。如果数字真的很大，你最终可能会添加成吨的鱼，那么我们如何克服它呢？好吧，到目前为止，您的最低答案是结果。如果您执行的操作比当前结果多，您将无法获得更好的操作，因此您可以结束循环并获得 return 结果。所以我们的复杂度是 O (n) - 数组的大小。无法想象一个更快的。编辑：实际上是 O (n log n) 因为排序。你可以递归地做所有事情（字面上的一切），但我真的不明白在这里这样做的意义。
我最近在面试中遇到了一个问题，我得到了一条鳄鱼的大小和一个代表池塘中鱼的大小的数组。 鳄鱼可以吃小于它大小的鱼，每次它吃掉那条鱼，它的大小就会随着那条鱼的大小而增加。我们可以对数组执行任意次数的两种类型的操作。
- 从池塘中取出所有鱼
- 向池塘添加任意大小的鱼
给定鳄鱼的初始大小和池塘中的鱼群，我们必须找到最小的编号。此类操作以清空表示池塘的数组。
例如-
鳄鱼的初始大小为 20，鱼的数组为
[10,15,20,30,100]
在这种情况下，鳄鱼吃掉了除 100 以外的所有鱼，它的大小变为 85，因此解决方案之一可能是移除大小为 100 的鱼。因此输出将为 1。
实现上述问题的最佳算法是什么，可以递归求解吗？
所以首先，对数组进行排序。鳄鱼会吃掉每条比他小的鱼。从左边开始，如果鳄鱼能吃到鱼，就增加它的体型。如果没有鱼了，return0。如果没有，做两个变量，一个潜在的结果=无穷大和动作=0。一个可能的答案是删除剩下的鱼。将结果设置为最小值（结果，fish_left + 操作）。然后尝试添加新鱼。你总是希望鳄鱼长得尽可能大，所以插入一条比鳄鱼小 1 的鱼（将它的大小乘以 2 再减 1）。将动作增加一个。让鳄鱼吃掉所有可能的鱼。重复直到所有的鱼都被吃掉，然后 return 结果。如果数字真的很大，你最终可能会添加成吨的鱼，那么我们如何克服它呢？好吧，到目前为止，您的最低答案是结果。如果您执行的操作比当前结果多，您将无法获得更好的操作，因此您可以结束循环并获得 return 结果。所以我们的复杂度是 O (n) - 数组的大小。无法想象一个更快的。编辑：实际上是 O (n log n) 因为排序。你可以递归地做所有事情（字面上的一切），但我真的不明白在这里这样做的意义。