P**********k
发帖数: 1629 | 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) 的算法，谢谢。 |
s******y
发帖数: 416 | 2 It is equivalent to the problem of finding medians of two sorted arrays.
task
hold
,
This
water,
【在 P**********k 的大作中提到】
: 问一下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,
|
P**********k
发帖数: 1629 | 3 不太明白，能否展开说说
我感觉大概的意思是类似quick sort.
先从red jug里面选择一个r1，然后用这个r1作为pivot把blue jugs分成两部分，一部
分set1包含所有比r1小的jug，另一部分set2包含所有比r1大的jug
然后从red jug里面再选择一个r2，这次先和之前的r1比较，这样就可以确定，只需要
在set1或者set2中搜索，
可是我的问题是，如果要是代码实现的话，是不是需要一个类似于binary tree的结构
来存储之前的pivot list，这样每次可以对于新的red jug，先在这个pivot list里面
搜索，来确定要partition的interval。。。
有做过这个的xdjm能来讨论一下么
【在 s******y 的大作中提到】
: It is equivalent to the problem of finding medians of two sorted arrays.
:
: task
: hold
: ,
: This
: water,
|
q****m
发帖数: 177 | 4 两个红的之间不能比较吧，题目里说能进行的操作只能是比较一个蓝的和一个红的。
【在 P**********k 的大作中提到】
: 不太明白，能否展开说说
: 我感觉大概的意思是类似quick sort.
: 先从red jug里面选择一个r1，然后用这个r1作为pivot把blue jugs分成两部分，一部
: 分set1包含所有比r1小的jug，另一部分set2包含所有比r1大的jug
: 然后从red jug里面再选择一个r2，这次先和之前的r1比较，这样就可以确定，只需要
: 在set1或者set2中搜索，
: 可是我的问题是，如果要是代码实现的话，是不是需要一个类似于binary tree的结构
: 来存储之前的pivot list，这样每次可以对于新的red jug，先在这个pivot list里面
: 搜索，来确定要partition的interval。。。
: 有做过这个的xdjm能来讨论一下么
|
p*****p
发帖数: 379 | 5 第二步里用那个等于r1的蓝壶把红色的分成两半，总共操作了O（n）
接下来红色上半和蓝色上半比，下半和下半比
【在 P**********k 的大作中提到】
: 不太明白，能否展开说说
: 我感觉大概的意思是类似quick sort.
: 先从red jug里面选择一个r1，然后用这个r1作为pivot把blue jugs分成两部分，一部
: 分set1包含所有比r1小的jug，另一部分set2包含所有比r1大的jug
: 然后从red jug里面再选择一个r2，这次先和之前的r1比较，这样就可以确定，只需要
: 在set1或者set2中搜索，
: 可是我的问题是，如果要是代码实现的话，是不是需要一个类似于binary tree的结构
: 来存储之前的pivot list，这样每次可以对于新的red jug，先在这个pivot list里面
: 搜索，来确定要partition的interval。。。
: 有做过这个的xdjm能来讨论一下么
|
M*******a
发帖数: 1633 | 6 这不是就是quick sort马，上面水平堪忧阿 |
