Note 3 升级成棒棒糖就能root了？# PDA - 掌中宝
P*k
1 楼
问一下CLRS里面一道题
Water Jugs Problem大概是在sorting那一章
There are n red & n blue jugs of different sizes and shapes. All red jugs
hold different amounts of water as the blue ones. For every red jug, there
is a blue jug that holds the same amount of water, and vice versa. The task
is to find a grouping of the jugs into pairs of red and blue jugs that hold
the same amount of water.
Operation allowed: Pick a pair of jugs in which one is red and one is blue,
fill the red jug with water and then pour the water into the blue jug. This
operation will tell you whether the red or the blue jug can hold more water,
or if they are of the same volume. Assume that such a comparison takes one
time unit. Your goal is to find an algorithm that makes a minimum number of
comparisons to determine the grouping.
要找到一个O(n lgn) 的算法，谢谢。
Water Jugs Problem大概是在sorting那一章
There are n red & n blue jugs of different sizes and shapes. All red jugs
hold different amounts of water as the blue ones. For every red jug, there
is a blue jug that holds the same amount of water, and vice versa. The task
is to find a grouping of the jugs into pairs of red and blue jugs that hold
the same amount of water.
Operation allowed: Pick a pair of jugs in which one is red and one is blue,
fill the red jug with water and then pour the water into the blue jug. This
operation will tell you whether the red or the blue jug can hold more water,
or if they are of the same volume. Assume that such a comparison takes one
time unit. Your goal is to find an algorithm that makes a minimum number of
comparisons to determine the grouping.
要找到一个O(n lgn) 的算法，谢谢。
