# Leetcode 解題速記 458. Poor Pigs
###### tags: `LeetCode` `C++`
題敘:
---
There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous.

You can feed the pigs according to these steps:

Choose some live pigs to feed.
For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time.
Wait for minutesToDie minutes. You may not feed any other pigs during this time.
After minutesToDie minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
Repeat this process until you run out of time.
Given buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to figure out which bucket is poisonous within the allotted time.

Example 1:

Input: buckets = 1000, minutesToDie = 15, minutesToTest = 60
Output: 5

Example 2:

Input: buckets = 4, minutesToDie = 15, minutesToTest = 15
Output: 2

Example 3:

Input: buckets = 4, minutesToDie = 15, minutesToTest = 30
Output: 2

測資範圍:
---
* `1 <= buckets <= 1000`
* `1 <= minutesToDie <= minutesToTest <= 100`

解題筆記:
---
這題考驗的不是演算法，反而是題目分析的能力。

首先，假設我們需要至少p隻豬來測試出在N桶buckets中有毒的那一桶，而在時間結束前總共能嘗試的次數T則可以用全部時間除以每次測試花費的時間來計算，意即
>`T = ( minutesToTest / minutesToDie )`。

這邊要注意的是，每T個測試我們都能得出T+1個結果，因為在可能的結果中，豬隻可以在第1到第T次測試中死亡，也可以最後生還，也就是第T+1個結果。因此，在p隻豬都有T+1種結果的情況下，所有豬隻就能得出`(T+1)^p`種結果。

之後根據題目的需求，可以列出一個不等式 : `(T+1)^p >= N`，等號兩側都取log之後就可以用程式碼進行實作了，此處用到ceil函式來做無條件進位。

程式碼:
---

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