s*********s 发帖数: 318 | 1 SF某startup coding test题
假设一个文件里包括某城所有餐馆的菜名和价钱。格式是 餐馆ID,价钱,菜名(包括
combo)。
1, 7.50, a
1, 12.50, a, b
1, 5.00, c
2, 8.00, a
2, 5.00, b
2, 9.00, b, d
程序要求:给定一个order, 输出最便宜的餐馆ID和总价。
order: a b, 输出 1 12.50
order: e, 输出 null
order: d, 输出 2 9.00 | r*******e 发帖数: 7583 | 2 只能想到brute-force的
把菜单做成一个菜或者combo做index的hashmap
对于order
求 all partitions of a set (including crossing partitions)
然后对每个partition求总价
【在 s*********s 的大作中提到】 : SF某startup coding test题 : 假设一个文件里包括某城所有餐馆的菜名和价钱。格式是 餐馆ID,价钱,菜名(包括 : combo)。 : 1, 7.50, a : 1, 12.50, a, b : 1, 5.00, c : 2, 8.00, a : 2, 5.00, b : 2, 9.00, b, d : 程序要求:给定一个order, 输出最便宜的餐馆ID和总价。
| s*********s 发帖数: 318 | 3 我也只能想到brute-force。order本身可能有duplicates: a b a c | s******s 发帖数: 31 | 4 可不可以从不同餐馆order?多order?有combo就要用dp吧。这道和usaco 3.3
shopping offers大同小异。如果可以多order,并且
要输出餐馆id的话,会稍麻烦点。 | s*********s 发帖数: 318 | 5 只能选一家最便宜的餐馆。
如果有DP思路的话,详细说说。
【在 s******s 的大作中提到】 : 可不可以从不同餐馆order?多order?有combo就要用dp吧。这道和usaco 3.3 : shopping offers大同小异。如果可以多order,并且 : 要输出餐馆id的话,会稍麻烦点。
| s******s 发帖数: 31 | 6 个人看法,每个餐馆都用dp算最便宜的买法。就是n-d weighted knapsnack。如果一共
有n种菜,那建立一个n-dimensional matrix。每个dimension对应一道菜。每个
dimension的index是一道菜的数量。matrix的值是能买到的最低的价格。与一般
knapsack不同之处是需要处理多买的情况。今天没时间写code,你可以先看看类似的题
,希望对你有帮助。 | p*****2 发帖数: 21240 | 7 combo没看懂
2, 9.00, b, d
order: d, 输出 2 9.00
只order d的话为什么跟combo一个价钱呢? | s*********s 发帖数: 318 | 8 因为只有那个combo含d.
【在 p*****2 的大作中提到】 : combo没看懂 : 2, 9.00, b, d : order: d, 输出 2 9.00 : 只order d的话为什么跟combo一个价钱呢?
| p*****2 发帖数: 21240 | 9
为什么不return null呢?
感觉更make sense。
【在 s*********s 的大作中提到】 : 因为只有那个combo含d.
| s*********s 发帖数: 318 | 10 题目要求,可以多order.
【在 p*****2 的大作中提到】 : : 为什么不return null呢? : 感觉更make sense。
| | | p*****2 发帖数: 21240 | 11
多order可以。我的意思是我要order一个d,结果你给我送来个combo就不对了吧。系统
可以提示不能这么order更合理吧。
【在 s*********s 的大作中提到】 : 题目要求,可以多order.
| s*********s 发帖数: 318 | 12 不管合不合理,这个题目要求输出含d的餐馆id.
【在 p*****2 的大作中提到】 : : 多order可以。我的意思是我要order一个d,结果你给我送来个combo就不对了吧。系统 : 可以提示不能这么order更合理吧。
| p*****2 发帖数: 21240 | 13
1, 7.50, a
1, 12.50, a, b
1, 5.00, c
2, 8.00, a
2, 5.00, b
2, 9.00, b, d
order可以随便下吧?比如a,b,d
【在 s*********s 的大作中提到】 : 不管合不合理,这个题目要求输出含d的餐馆id.
| s*********s 发帖数: 318 | 14 是啊。如果是input_data,return因该是:
2 17.00
【在 p*****2 的大作中提到】 : : 1, 7.50, a : 1, 12.50, a, b : 1, 5.00, c : 2, 8.00, a : 2, 5.00, b : 2, 9.00, b, d : order可以随便下吧?比如a,b,d
| p*****2 发帖数: 21240 | 15
结果必须是一个饭店,还是可以几个饭店混合呀?
【在 s*********s 的大作中提到】 : 是啊。如果是input_data,return因该是: : 2 17.00
| s*********s 发帖数: 318 | | p*****2 发帖数: 21240 | 17
如果一个饭店menu不全,就返回null了吧?
【在 s*********s 的大作中提到】 : 必须是一个饭店
| h**6 发帖数: 4160 | | s*********s 发帖数: 318 | 19 是的
【在 p*****2 的大作中提到】 : : 如果一个饭店menu不全,就返回null了吧?
| s*********s 发帖数: 318 | 20 写了个brute-force。总觉得不应该是这样。 | | | p*****2 发帖数: 21240 | 21
可以一个饭店一个饭店的算。算一个饭店就算bruteforce的话也是很快的。一个饭店的
menu实在是有限。
把常出现的order可以做个cache,不用重复计算了。
【在 s*********s 的大作中提到】 : 写了个brute-force。总觉得不应该是这样。
| r*******e 发帖数: 7583 | 22 二爷啊,从饭店的利益出发,这种情况肯定是返回combo啊,怎么能不让order
【在 p*****2 的大作中提到】 : : 可以一个饭店一个饭店的算。算一个饭店就算bruteforce的话也是很快的。一个饭店的 : menu实在是有限。 : 把常出现的order可以做个cache,不用重复计算了。
| p*****2 发帖数: 21240 | 23
如果这样的话,customers要complain了。我估计十有八九要退货了。至少我是不能容
忍这个的。
【在 r*******e 的大作中提到】 : 二爷啊,从饭店的利益出发,这种情况肯定是返回combo啊,怎么能不让order
|
|