娱乐 奇怪的算法挑战【第②期？】寻找宝物

[Caster库丘林]

大致理解了一下

卷轴适量的情况下需要合理规划使用

[t/c]代表的是步数，在[t/c]足够大的时候，显然最优解是二分法，对应的检查次数为[log₂n]或者[log₂n]+1

但当步数受到限制的时候，就需要考虑如何一步完成判断

一次对n个宝箱进行区分，本质上就是n个良品里找一个赝品的模型

目标是保证一次找出的同时使用的卷轴尽量少，此时对应的检查次数为n-[n/2]

综上，在步数富余的情况下缩小n的范围，再一次锁定，这样是消耗卷轴最少的方法

考虑到同一地牢内卷轴可以重复使用，那么最少的卷轴损耗就是max(x,y-[y/2])，其中x=[log₂n],y=[n/(2^x)]

而非酋的损耗甚至会高达x'+y'-[y'/2]，其中x'=[log₂n]+1,y'=[n/(2^x')]+1，可以说非常让人痛心了

十二月 16, 2021，由Caster库丘林修改