algorithm - 如何决定这个算法的逻辑

Question

这个问题想了半天，求助。谢谢

您从事食品物流业务。你有 N 个水 jar ，每个水 jar 的容量都是无限的。最初，每个 jar 正好装 1 升果汁。你想把这些水 jar 运到一个交货地点，但你一次只能运 K 个水 jar 。你不想浪费任何果汁，也不想多走一趟，所以你决定重新分配水壶里的东西，直到你最终得到不超过 K 个非空水壶。

您只能使用以下方法重新分配果汁。首先，挑选两个装有等量果汁的水壶。然后，将其中一个 jar 中的全部内容物倒入另一个 jar 中。根据需要多次重复此过程。

由于此限制，仅使用您最初拥有的 N 个水 jar 可能无法最终得到不超过 K 个非空水 jar 。幸运的是，您还可以购买更多水壶。您购买的每个水壶都恰好包含 1 升果汁，并且容量没有限制。例如，考虑 N 为 3，K 为 1 的情况。不可能从 3 个 jar 变成 1 个 jar 。如果你将一个 jar 倒入另一个 jar ，你最终会得到一个 2 升的 jar 和一个 1 升的 jar 。那时，你被困住了。但是，如果您随后购买另一个水壶，则可以将那个水壶倒入 1 升的水壶中，然后将得到的 2 升水壶倒入另一个 2 升的水壶中，最后只剩下一个 4 升的水壶。

返回为实现您的目标必须购买的最少数量的额外水壶。如果不可能，则返回 -1。

约束

– N 介于 1 和 10^7 之间，包括端值。

– K 介于 1 和 1000 之间，包括端值。 例子 1) 输入 3个 1个 输出 1个 (问题陈述中的示例。) 2) 输入 13 2个 输出 3个 (如果你有 13、14 或 15 个水 jar ，你不能以一两个水 jar 结束。如果有 16 个水 jar ，你可以以一个水 jar 结束。) 3) 输入 1000000 5个 输出 15808

Answer 1

这是一个优化的解决方案。它使用数字的二进制表示来查找所需的水壶数量(如其他人所述)。为了计算成本，它使用了这样一个事实，即在二进制表示中将 1 更改为 0 的成本会呈指数增长，因此一旦找到它们，将 1 更改为 0 总是更便宜。它的时间复杂度是 O(log(n)^2)。

function solve(n, k) {
   let binRep = [];
   let sumJugs = 0;
   while(n>0) {
      binRep.push(n%2);
      sumJugs += n%2;
      n = parseInt(n/2);
   }
   let cost = 0;
   while (sumJugs > k) {
      let idx = binRep.indexOf(1);
      cost += Math.pow(2, idx);
      while (binRep[idx] == 1 && idx < binRep.length) {
         sumJugs--;
         binRep[idx++] = 0;
      }
      if (idx >= binRep.length) binRep.push(1);
      else binRep[idx] = 1;
      sumJugs++;
   }
   return cost;
}