algorithm - 对两个单调递增数组进行二分搜索？

Question

假设我们有两个单调递增的数组

x = 50, 78, 103, 117, 130, 137, 143, 146, 149, 151, 153, 154, 155  
y = 62, 93, 108, 116, 121, 125, 128, 130, 131, 132, 133

x的每次移动花费 1 个硬币，y 花费 2 个硬币。
我们需要回答使用两个数组求和K所需的最低成本。

m1*x + m2*y >= K
where m1 and m2 are number of moves.

例如K=238那么，

• 从 x 所需的最小移动次数为5，即直到 130，其成本为 5 * 1 = 5（x 中每次移动的成本为 1）。
• 从 y 开始所需的最小移动次数为3，即直到 108 次，其成本为3 * 2 = 6（y 中每次移动的成本为 2）。

这给了我们总和238和最低成本5 + 6 = 11。

1. 一种方法是使用两个指针。
2. 如何使用二进制搜索来解决此类问题？

标签： algorithmbinary-search