---

題目

有 n 桶液體，其其中 正好 有一桶含有毒藥，其裝的都是水。它們從外觀看起來都一樣。為了弄清楚哪只水桶含有毒藥，你可以喂一些豬喝，通過觀察豬是否會死進行判斷，實驗對象的反應時間為 d 。不幸的是，你只有 t 時間來確定哪桶液體是有毒的。

解析

香農熵公式

根據題意，最大測試次數為 num = $|\frac{t}{d}|$

只測試一輪：

考慮 num=1 時，也就是只進行一輪測試，容易想到可以使用與水同等數量的小豬來進行測試，n 個小豬喝 n 桶液體，哪個死翹翹哪一桶水有問題。

但這樣的測試方式效率過低，我們其實可以結合二進制，讓每個小豬同時測試多桶液體。這樣禍害的小豬會少一點，更人道一些~

具體來說，我們需要 k 只小豬，k 滿足 $2^k\ge n$。舉個例子，當 n=5 時，可得 k = 3，即 3 只小豬即可一輪測出哪一桶是毒藥，具體做法：

1. 我們以 $x_1{x}_2{x}_3$ 的形式表示 5 桶液體的 二進制 編號，如：第一桶液體二進制編號為 001 。
2. 我們讓第 i 只小豬喝二進制編號 $x_i$ 為 1 的液體。即：
   • 第一只小豬需要喝的桶二進制編號為：100、101
   • 第二只小豬需要喝的桶二進制編號為：010、011
   • 第三只小豬需要喝的桶二進制編號為：001、011、101
3. 經過反應時間 d 后，觀察所有小豬的狀態，第 i 只小豬死亡則代表含毒的水桶其 編號第 i 位為 1 ，幸存則代表 編號第 i 位為 0 。從而得到含毒的水桶的編號。舉例：第二、三只小豬死亡，說明第三桶液體含毒；第一、三只小豬死亡，說明第五桶液體含毒……

測試 num 輪：

1. 只測試一輪時我們用二進制為水桶編號，因此測試 num 輪時，我們用 num+1 進制為水桶編號。
2. 小豬數量 k 需滿足 $(num+1{)}^k\ge n$，即 k 為 num+1 進制的長度。
3. 若某桶水的 num+1 進制中的第 x 位為 i（0<=i<=num），則代表將該水在第 i 輪喂給編號為 x 的小豬。

這樣我們就得到了著名的 香農熵 公式：$H(X)=?\sum _x{P(x)log}_2[P(x)]$

P(x) 代表隨機事件 x 的發生概率。

本題中，記隨機事件 A 為 n 桶液體中哪一個桶有毒，概率為 $\frac{1}{n}$ 。

記隨機事件 B 為在測試輪數為 num 時，所有實驗對象的最終狀態，每個實驗對象的狀態共有 num+1 種（一開始都是活的狀態，每測一輪多一種狀態的可能性——死 or 繼續活），即 k 只小豬共有 $C=(num+1{)}^k$ 種最終結果，可近似看做等概率 $\frac{1}{C}$ 。

我們需要求得在滿足 $H(A)<=H(B)$ 前提下的最小 k 值。即：$\frac{lo{g}_{2}n}{lo{g}_2(num+1)}<=k$

---

樣例具體分析

假設：總時間 minutesToTest = 60，死亡時間 minutesToDie = 15，pow(x, y) 表示 x 的 y 次方，ceil(x) 表示 x 向上取整。

那么：

1. 當前有 1 只小豬的話，最多可以喝 num = minutesToTest / minutesToDie = 4 次水
2. 最多可以喝 4 次水，能夠攜帶 base = times + 1 = 5 個的信息量，也就是：
   • 喝 1 號死去，1 號桶水有毒
   • 喝 2 號死去，2 號桶水有毒
   • 喝 3 號死去，3 號桶水有毒
   • 喝 4 號死去，4 號桶水有毒
   • 喝了上述所有水依然活蹦亂跳，5 號桶水有毒
   • 反推得，當 buckets ≤ 5 時，小豬數量 answer = 1 。
3. 那么 2 只小豬可以驗證的范圍最多到多少呢？我們把每只小豬攜帶的信息量（能測多少桶液體）看成是 base ，2 只小豬的信息量就是 $pow(base,2)=pow(5,2)=25$，所以當 $5\le buckets\le 25$ 時，anwser = 2 。
4. 那么可以得到公式關系：$pow(base,ans)\ge buckets$，取對數后即為：$ans\ge \frac{log(buckets)}{log(base)}$，因為 ans 為整數，所以 $ans=ceil(\frac{log(buckets)}{log(base)})$

---

代碼

class Solution {
public:int poorPigs(int buckets, int minutesToDie, int minutesToTest) {int num = minutesToTest/minutesToDie;return (int)ceil(log(buckets) / log(num+1));}
};