Let's say we have two monotonically increasing arrays
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
Each move of x costs 1 coin and y costs 2 coins.
We need to answer the minimum cost required using both arrays to make sum K.
m1*x + m2*y >= K
where m1 and m2 are number of moves.
For example K=238 then,
- Minimum number of moves required from x is 5 i.e till 130 which costs 5 * 1 = 5 (cost of each move in x is 1).
- Minimum number of moves required from y is 3 i.e till 108 which costs 3 * 2 = 6 (cost of each move in y is 2).
This gives us total sum 238 and minimum cost 5 + 6 = 11.
- One approach is to use two pointers.
- How can I use binary search to solve this kind of question?
Aucun commentaire:
Enregistrer un commentaire