458. 可憐的小豬

有 buckets 桶液體，其中 正好 有一桶含有毒藥，其余裝的都是水。它們從外觀看起來都一樣。為了弄清楚哪只水桶含有毒藥，你可以喂一些豬喝，通過觀察豬是否會死進行判斷。不幸的是，你只有?minutesToTest 分鐘時間來確定哪桶液體是有毒的。

喂豬的規則如下：

選擇若干活豬進行喂養

可以允許小豬同時飲用任意數量的桶中的水，并且該過程不需要時間。

小豬喝完水后，必須有 minutesToDie 分鐘的冷卻時間。在這段時間里，你只能觀察，而不允許繼續喂豬。

過了 minutesToDie 分鐘后，所有喝到毒藥的豬都會死去，其他所有豬都會活下來。

重復這一過程，直到時間用完。
給你桶的數目 buckets ，minutesToDie 和 minutesToTest ，返回在規定時間內判斷哪個桶有毒所需的 最小 豬數。

示例 1：輸入：buckets = 1000, minutesToDie = 15, minutesToTest = 60 輸出：5示例 2：輸入：buckets = 4, minutesToDie = 15, minutesToTest = 15 輸出：2示例 3：輸入：buckets = 4, minutesToDie = 15, minutesToTest = 30 輸出：2

提示：

• 1 <= buckets <= 1000
• 1 <=?minutesToDie <=?minutesToTest <= 100

解題思路

• 老鼠試毒藥的變種題目
  1024瓶毒藥，10只老鼠，試出一瓶有毒的毒藥，方案：給每瓶藥從0-1023進行編號，老鼠從0-9進行編號，對于每一瓶藥，根據其編號二進制表示中1出現的位置，給對應位置的小白鼠喂藥，根據小白鼠的死亡結果，可以反推出毒藥的二進制表示。

共通點：小白鼠只有兩種狀態0代表存活，1代表死亡，而本題中可以進行minutesToTest / minutesToDie輪，假如minutesToTest / minutesToDie=2的話，那么可以進行兩輪，存在3種狀態

第一輪死亡

第二輪死亡

第二輪還存活

老鼠試藥的計算公式為 $2^{10}=1024$

• 1024 為毒藥數量
• 2為老鼠可能的狀態數量
• 10 代表老鼠個數

因此這題 計算公式為$state{s}^{res}=buckets$

• buckets 為毒藥數量
• states為小豬可能的狀態數量，公式為minutesToTest / minutesToDie + 1;
• res為需要的小豬數量，也是我們需要計算的最終結果

代碼

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

總結

以上是生活随笔為你收集整理的458. 可怜的小猪的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。