如何使用二进制搜索解决 SPOJ : SCALE？

Question

http://www.spoj.com/problems/SCALE/ 我正在尝试使用递归来做到这一点，但得到了 TLE。问题的标签是 BINARY SEARCH。如何使用二进制搜索来做到这一点？提前致谢。

Answer 1

这里首先要注意的是，如果每个尺寸有两个个权重而不是一个，那么问题就很简单了，因为我们只需要表示X 在其基础 3 表示中并取相应数量的权重。例如，如果 X=21 那么我们可以取两次 P_3 和一次 P_2，然后将它们放入另一个尺度。

现在让我们尝试做一些类似的事情，利用我们可以添加到两个尺度（包括放置X的那个）的事实：

假设X <= P_1+P_2+...+P_n，那就意味着X <= P_n + (P_n-1)/2（很容易理解为什么）。因此，X + P_(n-1) + P_(n-2)+...+P_1 < 2*P_n。

(*) What that means is that if we add some of the weights from 1 to n-1 to same scale as X, then the number on that scale still does not have 2 in its n-th rightmost digit (either 0 or 1).

从现在开始假设 digit 表示其 base-3 表示中的数字（但它可以暂时变得大于 2 :P ）。现在让我们将第一个秤（放置 X 的位置）的总重量表示为 A=X，另一个秤是 B=0，我们的目标是使它们相等（两个 A B 会随着我们的进步而改变）。让我们从最小到最大（最左边）遍历 A 的所有数字。如果当前数字索引是 i 并且它：

等于0然后忽略并继续
等于1 然后我们将权重 P_i=3^(i-1) 放在体重秤 B 上。
等于2然后我们加上P_i=3^(i-1)来缩放A。请注意，这将导致数字 (i+1).
等于3（是的，这种情况是可能的，如果当前和前一个数字都是2）将1添加到索引i+1处的数字并进一步（没有重量被添加到任何规模）。

由于 (*) 显然程序将运行正确（因为最后一位数字将等于 A 中的 1），因为我们将只选择一个从集合中取重并正确放置它们，显然在程序完成后数字 A 和 B 将相等。

现在是第二种情况X > P_1+P_2+...+P_n。显然，即使我们将所有权重都放在第二个天平上，我们也无法平衡。

这完成了证明并显示了何时可能以及如何将权重放置在两个尺度上以使其相等。

编辑:

C++我刚才在SPOJ提交成功的代码https://ideone.com/tbB7Ve

Answer 2

这个问题的解决方案非常简单。这个想法与@Yerken 的回答相同，但表达方式有点不同：

只有第一个砝码的质量不能被 3 整除。所以第一个砝码是唯一对平衡 mod 3 属性 2 个天平有影响的：
- 如果X mod 3 == 0，则一定不能使用第一个权重
- 如果 X mod 3 == 1，第一个重量必须在秤 B 上（当前为空）
- 如果 X mod 3 == 2，第一个重量必须在秤 A
两个尺度都减去权重 (B) --> 解不变，现在权重 (A) 可以被 3 整除，而权重 (B) == 0
设置 X' = weight(A)/3 并将每个权重 Pi 除以 3 ==> 解决方案不变，现在 N' = N-1 和 X' = (X +1)/3

伪代码：

listA <- empty
listB <- empty
for i = 1 to N {
  if (X == 0) break for loop; // done!
  if (X mod 3 == 1) then push i to listB;
  if (X mod 3 == 2) then push i to listA;
  X = (X + 1)/3;  // integer division
}
hasSolution <- (X == 0)

C++代码：http://ideone.com/LXLGmE

如何使用二进制搜索解决 SPOJ : SCALE？

How to solve SPOJ : SCALE using binary search?

algorithm

dynamic-programming

brute-force

binary-search

scale