猿辅导笔试算法第三题讨论
题目:小猿在玩一个游戏,给定一个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++会不会超时。
#笔试题目##猿辅导#