一道算法或者逻辑面试题,求思路

100个面值是1-50随机分布的硬币排成一列,你和另一个人一人一个的取,只能从队列头部和尾部取。如何保证最后你取的硬币面值和比你对手多?

1个回答

保证你取倒数第二张?
还是和最大?
1~50 面值按照谁家的硬币?
美元?

美元面值:
现流通硬币有1 分、5 分、10分、1/4 元、1/2 元、1 元六种面值。
正面与背面所铸图案如下:
1 分 - 正面: Lincoln 林肯 ,背面:林肯纪念堂 5 分 - 正面:Jefferson 杰佛逊 ,背面:杰斐逊的故居

10分 - 正面: Roosevelt 罗斯福 ,背面:火炬,橄榄枝,橡树枝 1/4 元 - 正面:Washington 华盛顿 ,背面: 白头鹰
1/2 元 - 正面:Kennedy 肯尼迪 ,背面:总统专用国徽 1 元 - 正面:Sacagawea 莎卡嘉薇亚 ,背面:飞翔中的白头鹰
此外还发行过采用这六种面值的与上述图案不同的硬币,及5 分、10分、1/4 元、1/2 元、1 元面值的纪念币。
以前还发行过3分的硬币,现已不能流通。

人民币硬币面值
1分,2分,5分,(退出流通了)
1角,5角,1元(正在用):

既然是双端队列,你可以取走当期最大价值的,换成对手,也是如此,如果是求和的话,两种取法选最大,这是01背包
如果是最后一次面值最大,采用中间向两头扩展的办法从而保证能取到最大的

lm_whales
lm_whales 最优解那个,效率太低,可能会堆栈溢出,但求出的结果是最优结果。
4 年多之前 回复
lm_whales
lm_whales 效率要高的多,但不一定是最优解
4 年多之前 回复
lm_whales
lm_whales 有一个局部最优的方法,可是不能保证结果一定是最优的(可能 你获得超额利益,也可能对手,但是多数情况下,是最优的结果)
4 年多之前 回复
lm_whales
lm_whales 有一个思路,但是效率太低了,我在考虑一下能否改进改进
4 年多之前 回复
u010759408
一只安静的猪 您好,最后是所有硬币和最大;硬币和人民币和美元没太大关系,取值从1-50即可;不知道是否能详细描述下思路,谢谢
4 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐