题意:给你一些数量的桶buckets,已知某一个桶里有毒药,猪在喝了毒药后一定时间内minutesToDie会死亡,给一个规定时间minutesToTest,问最少需要多少猪才能唯一确定毒药在哪个桶里。
解题思路:开始的时候总想着二分查找,二分的思路还不是最快的,最快的是根据位就像二进制位来确定桶的位置。
如果死亡时间15min,规定在60min内确定毒药,共25个桶。因为15分钟揭露一次,所以60/15=4次,可以揭露4次,但可以做5次验证,因为如果前4次猪都没死,那肯定就是第五次会死,所以可以采用5进制对桶进行编码。
把桶编号为
00 01 02 03 04
10 11 12 13 14
30 31 32 33 34
40 41 42 43 44
50 51 52 53 54
在0分钟时第一只猪喝开头编码全为0的桶,第二只猪喝第二位编码全为0的桶;
15分钟后第一只猪喝第一位编码全为1的桶,第二只猪喝第二位编码全为1的桶;
............
每只猪守护一位编码,反正在规定时间内,一定可以得到自己守护的那位编码到底哪一个是有毒的,最后经过所有猪的合并,可以唯一标示一个桶有毒。
对题意来说,1000个桶,15分钟死亡时间,60分钟验证时间。
可以验证60/15 = 4次,所以可以采用5进制编码桶。
每增加一位,就增加一头猪;一位可以验证5桶,二位可以验证55=25桶,三位可以验证555=125桶,四位验证5555=600桶,五位可以验证3000桶。所以至少需要5头猪。
对桶的编码就是00000,00001,00002,00003,00004,00010,00011,00012....34234......
开始,第一头猪把第一位为0的全喝,第二头猪把第二位为0的全喝。。。
15分钟后第一头猪死了可以确定带毒的桶第一位编码为0,继续第二头猪把第二位为1的全喝。。。
60分钟后,根据猪死的情况,可以唯一对应一个编码即为有毒的桶的编码。
解题目:确定位数bits = minutesToTest/minutesToDie + 1;
确定猪的个数就是bits**猪个数 >=buckets.
class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
if(buckets == 1)
return 0;
int bits = minutesToTest / minutesToDie + 1;
int cnt = 1, nums = bits;
while(nums < buckets){
cnt++;
nums *= bits;
}
return cnt;
}
};
网友评论