猿辅导笔试算法第三题讨论

题目:小猿在玩一个游戏,给定一个n,代表一共有1,2,3...... n这些数字。正确的数字为其中的一个。他可以从里面任意挑选一个数字 x ,如果选错了,会知道这个数字比正确数字大了还是小了。并且消耗x个金币。他有k次机会免单,即不需要消耗金币。

求小猿要找到正确数字最少需要准备的金币。

输入:一行两个整数 n,k

示例:

输入:3 0
输出:2
第一次选择第二个数字,消耗两个金币。然后就知道正确数字在2左边还是右边,下一次一定能找到正确数字。


n,m=map(int,input().split())

cache={}
def dfs(l,r,k):
    if (l,r,k) in cache:
        return cache[(l,r,k)]
    if k>=r-l+1&nbs***bsp;l>=r:
        return 0
    res=1e9
    for i in range(l,r+1):
        if k!=0:
            res=min(max(dfs(l,i-1,k-1),dfs(i+1,r,k-1)),res)
        res=min(max(dfs(l,i-1,k)+i,i+dfs(i+1,r,k)),res)
    cache[(l,r,k)]=res
    return res

print(dfs(1,n,m))
dfs(l,r,k)代表在l,r区间之内有k次面单机会  至少需要准备的金币数量。

过了40%超时了,不知道c++会不会超时。
#笔试题目##猿辅导#
全部评论
这个用例就是故意恶心人的,哪怕给个4也不会往2分那边死磕。。。 具体参考leetcode375
1 回复
分享
发布于 2020-08-22 20:50

相关推荐

点赞 3 评论
分享
牛客网
牛客企业服务