[LeetCode][458]Poor Pigs題解

問題:https://leetcode.com/problems/poor-pigs/discuss/94266/Another-explanation-and-solution
1匹のブタは(minutesToTest/minutesToDie)+1個のバケツが有毒かどうかをテストすることができます2匹のブタに対して少なくとも(minutesToTest/minutesToDie)+1)^2のバケツの数をテストします
1つのバケツからなる2つの配列1 2 3 4 4 5 6 7 8 9 10 11 13 14 15 16 17 19 20 21 22 24ブタ1に対して1 2 3 4 5 6 7...10 11...15 16...20 21...25ブタ2に対して1 6 11 16 21...22 3...23 4...24...25
最後に2匹の豚が死亡した時間から毒薬がどのバケツの中にあるかを推定することができますeg.8-th bucketで、それでは

豚1は2番目の15分で

死亡した.

豚2は3番目の15分で

死亡した.

毒薬は必ず2列目、3行目は8

であることがわかります.
したがって、n匹のブタは(minutesToTest/minutesToDie)+1)^nバケツの水をテストすることができ、与えられたバケツの数についてpigの数->をテストして((minutesToTest/minutesToDie)+1)^n>バケツの数をテストすればよい
したがって、条件はpow(test,pigs)>=bucketsであり、test=(minutesToTest/minutesToDie)+1

/*
 * [458] Poor Pigs
 *
 * https://leetcode.com/problems/poor-pigs/description/
 *
 * algorithms
 * Easy (43.76%)
 * Total Accepted:    12.9K
 * Total Submissions: 29.4K
 * Testcase Example:  '1000
15
60'
 *
 * There are 1000 buckets, one and only one of them contains poison, the rest
 * are filled with water. They all look the same. If a pig drinks that poison
 * it will die within 15 minutes. What is the minimum amount of pigs you need
 * to figure out which bucket contains the poison within one hour.
 *
 * Answer this question, and write an algorithm for the follow-up general
 * case.
 *
 * Follow-up:
 *
 * If there are n buckets and a pig drinking poison will die within m minutes,
 * how many pigs (x) you need to figure out the "poison" bucket within p
 * minutes? There is exact one bucket with poison.
 *
 */
class Solution
{
  public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest)
    {
		int test=(minutesToTest/minutesToDie)+1;
		int pigs=0;
		while(pow(test,pigs)<buckets)
		{
			pigs++;
		}
		return pigs;
    }
};

問題解2:使用符号化理解:符号化解法参考リンク:https://blog.csdn.net/dianxin113/article/details/71713644?utm_source=blogxgwz0