大致理解了一下
卷轴适量的情况下需要合理规划使用
[t/c]代表的是步数,在[t/c]足够大的时候,显然最优解是二分法,对应的检查次数为[log2n]或者[log2n]+1
但当步数受到限制的时候,就需要考虑如何一步完成判断
一次对n个宝箱进行区分,本质上就是n个良品里找一个赝品的模型
目标是保证一次找出的同时使用的卷轴尽量少,此时对应的检查次数为n-[n/2]
综上,在步数富余的情况下缩小n的范围,再一次锁定,这样是消耗卷轴最少的方法
考虑到同一地牢内卷轴可以重复使用,那么最少的卷轴损耗就是max(x,y-[y/2]),其中x=[log2n],y=[n/(2^x)]
而非酋的损耗甚至会高达x'+y'-[y'/2],其中x'=[log2n]+1,y'=[n/(2^x')]+1,可以说非常让人痛心了