458. Poor Pigs
给你b个桶子
其中包含一个有毒的桶子
你一共有t分钟可以进行测试
然后你可以拿去让猪喝
喝到有毒的桶会让猪d分钟后死亡
正在等待中的猪不能再喝其他的桶
请问当有b个桶子 测试一次要d分钟 测验时间共t分钟的情况下
回传进行测试最少需要的猪只数量
Input: b = 4, d = 15, t = 15
Output: 2
让A猪喝1,2桶 B猪喝1,3桶
判断哪一桶有毒
A猪死亡:2桶
AB猪死亡:1桶
B猪死亡:3桶
没有猪死亡:4桶
Input: b = 4, d = 15, t = 30
Output: 2
我没有找到这一题的正确喂法
所以我没有解出来
这边先讲我的思路:
首先t跟d两个可以简化成可以测试的次数time
time = floor(t/d)
然后我们要找到怎么在有限次数内找到最佳解法
我想到的实验方法是类似双蛋问题的解决方法
可是这个方法不是最佳解
稍微讲一下思路就好
如果我们有5只猪 可以测验三次
那我们第一次可以把桶分六堆
让每只猪各喝其中一堆 看哪一只猪死掉 没死掉就是剩下一堆有毒
之后把剩下的桶分五堆 前四堆让四只猪测试
最后剩下三只猪 用binary的方法让猪混著喝 可以测试最多8桶
然后根据前面分堆
可以得到5只猪最多测试8*5*6=240桶
然后还要判断猪没死掉的话那一堆可以多测的桶数
但是这不是正解 我就没有研究下去了
网络上的正解:
先计算我们一共可以测验的次数time
如果time是4
代表我们可以分五堆
然后我们把桶子以二维的方式排列
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
接下来第一只猪第一次测验喝第一栏(1 6 11 16 21)
第二只猪第一次测验喝第一列(1 2 3 4 5)
测验四次之后看猪在什么时候死掉
如果第一只猪第三次测验死掉
第二只猪第四次测验死掉
代表第18桶有毒
都没死掉代表第25桶有毒
这个方法可以让我们透过两只猪及四次测验分辨25个桶哪个有毒
可以得到公式 (time + 1)^pig = bucket
但是我们要找的是猪的数量
所以pig = log(time+1)bucket
然后log有公式 log(A)B = logB / logA
TS code:
function poorPigs (b: number, d: number, t: number): number {
const r = Math.log(b) / Math.log(Math.floor(t / d) + 1)
return r - Math.floor(r) > 0.001 ? Math.ceil(r) : Math.floor(r)
}
我在交答案的时候被TypeScript搞了一次
因为TS没有整数 只有浮点数
我加一加冒出一个3.00000000000004