leetcode 458 可怜小猪

461c35ab3c0361027fa35c9f4c65a04.png
对于一只猪，可以在1h之内最多喝 4次水(60/15)，但是可以检验5个桶，如果前四次没死，说明第5个桶有毒。
对于2只猪，现在可以让一只猪一下喝5桶水，如图所示的一只猪喝行的五个，一只猪喝列的五个，这样就可以确定哪个桶有毒。
对于3只猪，就是三维的 5 X 5 X 5 ，可以检测125个桶；

  1. class Solution {
  2. public:
  3.     int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
  4.         if(buckets<=1) return 0;
  5.         int times=minutesToTest/minutesToDie+1;
  6.         int reg_times=times;
  7.         int pig=1;
  8.         while(times<buckets){
  9.             times*=reg_times;
  10.             pig++;
  11.         }
  12.         return pig;
  13.     }
  14. };

小鼠试药

现有一千瓶药水，其中九百九十九瓶是完全一样的，只有一瓶里面是毒药，但是外观上分辨不出来。毒药给小白鼠喝了后，一星期后这只小白鼠会突然死亡，但之前一点症状也没有。现需要在一星期后找出哪瓶是毒药，问至少需要几只小白鼠？
答案
二进制问题，10只即可，10只最多可测试1024瓶药水
问题解析
瓶子编号：给每个瓶子用二进制编号，总共有1000瓶，2的10次方等于1024，只需用十位二进制就可表示所有的瓶子，每一位依次用w1、w2、…w10表示。
老鼠编号：十位二进制c1、c2、…c10分别给十只老鼠编号，
编号c1的老鼠只喝w1位上为1的药水瓶，编号c2的老鼠只喝w2位上为1的药水瓶，依次类推。最后看哪些老鼠死掉，例如c10、c8、c7、c4、c3、c1编号的老鼠死掉，那么有毒药水的编号就是10 1100 1101

简化一下：如果只有8瓶，至少需要几只老鼠？？？
药水瓶编号是000 001 010 011 100 101 110 111，
三位二进制w1、w2、w3
三只老鼠是c1、c2、c3，
老鼠c1、c2、c3与三位二进制w1、w2、w3一一对应
c3喝： 100 101 110 111(第三位是1的都喝)
c2喝： 010 011 110 111(第二位是1的都喝)
c3喝： 001 011 101 111(第一位是1的都喝)

最后假设c3死了，那么100是毒药
假设c3c2死了，那么110是毒药
c2c1死了，那么011是毒药，
类推，哪只老鼠死对应位上就是1，没死为0，得出的结果就是毒药瓶编号