返回信息流假设你现在有1000瓶药，其中有2瓶是有毒的，任意多份药混合只要其中有一份是有毒的就可以把老鼠毒死，求最少多少只老鼠可以在一轮实验中试出两瓶毒药的编号
补充说明：
1.一轮实验指的是必须在有小白鼠死亡的时刻就知道答案，而不能死了小白鼠再继续试验
2.此题思维难度较大，想看答案的同学可以跳转24楼
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #97014同步于 2018/10/29
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
求教一道题，1000瓶药和老鼠实验的变种
unsmilecat
2018/10/29镜像同步57 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
https://leetcode.com/problems/poor-pigs/description/
如果我没理解错的话和这道题应该是一样的
64只。
假设我有3瓶药，我需要2只老鼠，每只吃1瓶，可得出哪2瓶有问题
假设我有4瓶药，我需要3只老鼠，每只吃2瓶，可以得出哪一瓶有问题
A：1，2
B：2，3
C：3，4
假设我有6瓶药，我需要3只老鼠，每只吃4瓶。
A:1234
B:2345
C:3456
似乎解决不了问题。好，我们尝试加老鼠：
A：123
B：234
C：345
D：456
似乎还是解决不了问题，比如毒药是13或者23的情况下，都是ABC死掉。
可以推测，老鼠一次吃几瓶药和最终的数量是有关联的。
吃1瓶，老鼠数目等于药数目
吃2瓶，老鼠数目等于药数目-1
吃3瓶，我们来试试9瓶药会如何。一维基本没啥优化。
请脑补一个3*3的矩阵
1 | 2 | 3
---|---|---
4 | 5 | 6
7 | 8 | 9
尝试横着和竖着吃药看看。
A:123
B:456
C:789
D:147
E:258
F:369
惊人的发现，是可以根据一次吃药拿到哪两个有问题的。
补充一下，由于32*32>1000>31*31 矩阵中有一些格子就空着，老鼠不吃就好了，每个老鼠吃的药瓶数等于32
(ps:楼上说的poor pig也是这个思路)
所以大胆猜测结果是 老鼠数目开根号结果向上取整再乘2
这样好像提高了问题的复杂度，本来有1000瓶有2瓶有毒，一组合变成了999*500个样本中区别出999+998个有毒的瓶数了[ema13]
【 在 shisuan 的大作中提到: 】
: 任意两瓶药的组合一共有999*500种n只老鼠可以表示2^n种情况
: 所以答案应该是lg(500*999)只是编码方法未确定