algorithm - 给定 n 个硬币，其中一些更重，找到重的硬币的数量？

Question

给定 n 个硬币，其中一些更重，使用 O(log^2 n) 权重计算重硬币数量的算法。请注意，所有重硬币的重量相同，所有轻硬币的重量也相同。

你会得到一个天平，你可以使用它来比较两个不相交的硬币子集的重量。请注意，余额仅指示哪个子集更重，或者它们是否具有相同的权重，而不是绝对权重。

Answer 1

我不会给出完整的答案，但我会帮你分解它。

1. 找到一个O(log(n))算法来找到一个重的硬币。
2. 找到一种O(log(n))算法，将一个集合分成两组，其中重计数和轻计数的数量相同，再加上最多两个剩余部分（当每个集合的数量不相等时）。
3. 结合算法#1 和#2。

提示：

• 算法#1 独立于算法#2。
• O(log(n))二进制搜索的提示
• 你怎么可能最终O(log^2(n))得到两种O(log(n))算法？