给国内老人买安卓手机，那种合适？ - 未名空间MITBBS历史存档

给国内老人买安卓手机，那种合适？# PDA - 掌中宝

h*r2016-06-28 07:06

1 楼

标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
怎么做了。
输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
例子：
输入： 5 3
代表第一个水桶5L，第二个水桶3L
（输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
的容积可能相同）
那么输出
1: 4 最少4次操作得到1L水
2: 2
3: 1
4: 6
5: 1
如果无法得到x L的水，输出x: impossible
每次盛水必须装满该桶，从桶1导入桶2的时候，必须要么桶1倒光，要么桶2接满水
我这题只会做两个水桶的，就是不断把一个水桶装满然后倒入第二个水桶，看看当中出
现过那些容积的水
但是多个水桶的不太会做
各位有什么思路么

y*r2016-06-28 07:06

2 楼

买了rrc和rdn。

a*n2016-06-28 07:06

3 楼

不想买苹果。就是打电话，微信视频。
想买小米或者华为，请教哪款比较合适，性价比好。
多谢！

h*c2016-06-28 07:06

4 楼

两桶水曾经在电影die hard series 中一集出现
以后就很少见红博flex their brain

s*92016-06-28 07:06

5 楼

rdn is bad, isn't it?

【在 y***r 的大作中提到】

: 买了rrc和rdn。

j*e2016-06-28 07:06

6 楼

性价比当然是雷布斯的小米

【在 a****n 的大作中提到】

: 不想买苹果。就是打电话，微信视频。
: 想买小米或者华为，请教哪款比较合适，性价比好。
: 多谢！

s*52016-06-28 07:06

7 楼

interesting. why the answer is 4? 2*3-5 = 1, isn't it 2?

【在 h*********r 的大作中提到】

: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出

c*l2016-06-28 07:06

8 楼

did u cut your UNG

【在 y***r 的大作中提到】

: 买了rrc和rdn。

a*n2016-06-28 07:06

9 楼

就是想知道那个model啊。。。

【在 j***e 的大作中提到】

: 性价比当然是雷布斯的小米

l*h2016-06-28 07:06

10 楼

为什么1：4？
如果有1升的水桶呢？你的条件不是 1-20吗？
是不是这样的意思：５个水桶是随机给的，任意给定的每组水桶都要能产生出1升的测
量？然后其中操作最多的一个是4次？
修改：看来理解还是不对，给了5个20升水桶，怎么也不能产生1.
再修改：你要在1-20的水桶中找5个水桶（不能用和目标一样大的水桶），最快几次倒
腾就能得到目标。还是不对，我找一个3，一个2，一次操作不就完事了？1：1； 2：1
； 3：1.。。。
是我糊涂，没看到有给定的输入。
我的笨办法，是建立 table,
操作次数
T1： b1, b2, b3 b4, b5
T2: 所有bi+-T1
T3: 所有 bi+-T2
T4: ....
..

【在 h*********r 的大作中提到】

: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出

g*l2016-06-28 07:06

11 楼

抄RDN? SHORT SQUEEZE了会不会狂跌啊

a*n2016-06-28 07:06

12 楼

不是说果6侵权不能卖了吗？怎么京东上还都是？

h*r2016-06-28 07:06

13 楼

这个例子的输入是 5 3
代表第一个水桶5L，第二个水桶3L
输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的的
容积可能相同

：1

【在 l****h 的大作中提到】

: 为什么1：4？
: 如果有1升的水桶呢？你的条件不是 1-20吗？
: 是不是这样的意思：５个水桶是随机给的，任意给定的每组水桶都要能产生出1升的测
: 量？然后其中操作最多的一个是4次？
: 修改：看来理解还是不对，给了5个20升水桶，怎么也不能产生1.
: 再修改：你要在1-20的水桶中找5个水桶（不能用和目标一样大的水桶），最快几次倒
: 腾就能得到目标。还是不对，我找一个3，一个2，一次操作不就完事了？1：1； 2：1
: ； 3：1.。。。
: 是我糊涂，没看到有给定的输入。
: 我的笨办法，是建立 table,

y*r2016-06-28 07:06

14 楼

低买高卖。
刚才又买了一批 @ 8.15.

【在 c********l 的大作中提到】

: did u cut your UNG

j*t2016-06-28 07:06

15 楼

红米note3

【在 a****n 的大作中提到】

: 不想买苹果。就是打电话，微信视频。
: 想买小米或者华为，请教哪款比较合适，性价比好。
: 多谢！

h*r2016-06-28 07:06

16 楼

首先装满小桶，这时候两个桶水量为3,0
然后小桶倒入大桶，水量分别为0,3
装满小桶，3,3
小桶导入大桶，1,5
这时候小桶剩余1L
4次操作

【在 s***5 的大作中提到】

: interesting. why the answer is 4? 2*3-5 = 1, isn't it 2?

p*i2016-06-28 07:06

17 楼

co buy

t*n2016-06-28 07:06

18 楼

刚刚给老爸买了个小米5，用着很高兴。个人觉得小米的UI比华为用着舒服。另外别小
看老年人的学习能力。我家2老天天捧着手机跟同样岁数的老头老太太们聊微信开心得
很。

d*62016-06-28 07:06

19 楼

就是一个search的问题，bfs比较合适

y*r2016-06-28 07:06

20 楼

today is finance day, energy need wait.

p*m2016-06-28 07:06

21 楼

红米note3

B*t2016-06-28 07:06

22 楼

我还以为是脑筋急转弯。假设桶是圆柱体形状的话，把桶倾斜到刚好看到底面的时候，
剩余的水量刚好是1/2.
所以如果是3和5升的两个桶，那么用2.5-1.5就可以得到1升的水了。。
没看到必须倒满这个条件。感觉是很傻的一个题目。。

o*e2016-06-28 07:06

23 楼

说白了就是求一个整系数不定方程的整数解 .. a_0 x_0 + a_1 x_1 + .. + a_{n-1} x
_{n-1} = b, a_i 为桶的容积, b 为最终目标的水量
如果 b 是所有 a_i 的最大公约数及其倍数, 则 (可能) 有解; 否则无解

f*s2016-06-28 07:06

24 楼

基本同意这个，但是有两点细节需要优化，具体到下面两个例子，
例子1: 【5，3】
1:4
例子2: 【7，3】
1:4
例子1说明每次做加法count加 2，减法加1.例子2说明有时候减法也有加2。
我觉得可能需要分情况建立一个library，index是count，然后在library里search

：1

【在 l****h 的大作中提到】

: 为什么1：4？
: 如果有1升的水桶呢？你的条件不是 1-20吗？
: 是不是这样的意思：５个水桶是随机给的，任意给定的每组水桶都要能产生出1升的测
: 量？然后其中操作最多的一个是4次？
: 修改：看来理解还是不对，给了5个20升水桶，怎么也不能产生1.
: 再修改：你要在1-20的水桶中找5个水桶（不能用和目标一样大的水桶），最快几次倒
: 腾就能得到目标。还是不对，我找一个3，一个2，一次操作不就完事了？1：1； 2：1
: ； 3：1.。。。
: 是我糊涂，没看到有给定的输入。
: 我的笨办法，是建立 table,

v*12016-06-28 07:06

25 楼

桶太小

【在 h*********r 的大作中提到】

: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出

B*g2016-06-28 07:06

26 楼

这很像硬币凑数的题目啊，不过有减法，次数统计也不像数硬币那么直接，应该可以dp?

【在 h*********r 的大作中提到】

: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出

c*82016-06-28 07:06

27 楼

像DP
一个hashtable（L数，操作次数）
初始化，已有桶的L数，对应次数是1，其他是impossible
然后对已有的L数做相减操作，对应次数相加

【在 h*********r 的大作中提到】

: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出

a*u2016-06-28 07:06

28 楼

小桶装满 3L 倒入大桶（3L/5L）
再次装满小桶，倒满大桶 (2L+3L/5L),
最后剩下 1L 在小桶内

h*r2016-06-28 07:06

29 楼

题目不是就求这一个诶。。

【在 a***u 的大作中提到】

: 小桶装满 3L 倒入大桶（3L/5L）
: 再次装满小桶，倒满大桶 (2L+3L/5L),
: 最后剩下 1L 在小桶内

h*r2016-06-28 07:06

30 楼

up up up

i*y2016-06-28 07:06

31 楼

1. check if x is possible (as someone mentioned, x is only possible if it's
a multiple of greatest common divisor K of all buckets)
2. get max steps for each x (1 if x = bucket_i. For others, use max(bucket_i
) and bucket_j where their GCD is K. Repeatedly pour one to the other until
all x are found)
3. get min steps for each x. Use recursive method and try all possibilities,
dynamically update max steps for other x along the way. Number of recursive
depth can't exceed the max step for x.

【在 h*********r 的大作中提到】

: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]，水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出