美文网首页LeetCode蹂躏集
2018-06-07 458. Poor Pigs

2018-06-07 458. Poor Pigs

作者: alexsssu | 来源:发表于2018-06-07 20:13 被阅读0次

    题意:给你一些数量的桶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;
        }
    };
    

    相关文章

      网友评论

        本文标题:2018-06-07 458. Poor Pigs

        本文链接:https://www.haomeiwen.com/subject/rnrnsftx.html