LeetCode 每日一题 458. 可怜的小猪(Leetcode daily question 458. Poor little pig)

题目描述

buckets 桶液体,其中 正好 有一桶含有毒药,其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药,你可以喂一些猪喝,通过观察猪是否会死进行判断。不幸的是,你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

来源:力扣(LeetCode)
喂猪的规则如下:

  • 选择若干活猪进行喂养
  • 可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
  • 小猪喝完水后,必须有 minutesToDie 分钟的冷却时间。在这段时间里,你只能观察,而不允许继续喂猪。
    过了 minutesToDie 分钟后,所有喝到毒药的猪都会死去,其他所有猪都会活下来。
    重复这一过程,直到时间用完。
    给你桶的数目 buckets ,minutesToDie 和 minutesToTest,返回在规定时间内判断哪个桶有毒所需的 最小 猪数。

Solution

最优解法为,将所有的猪按照某进制编号,得到一个数字,每头猪确定这个数字的某一位即可。
这个进制数字怎么找呢?

显然我们的 \(猪的数量+1\) 就是我们的进制(base)。 然后我们可以得到的 最大的液体数量的范围为 \(ans \le base ^ {cnt}\)
因此

cnt = minutesToTest / minutesToDie
ans = ceil(log(buckets) / log(base));

AC_CODE

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

Title Description

There are < strong > buckets < / strong > barrels of liquid, one of which contains poison, and the rest is water. They all look the same from the outside. In order to find out which bucket contains poison, you can feed some pigs and judge by observing whether the pigs will die. Unfortunately, you only have  < Strong > minutestotest < / strong > minutes to determine which barrel of liquid is toxic.

Source: leetcode
The rules for feeding pigs are as follows:

  • Several live pigs were selected for feeding
  • Piglets can be allowed to drink any number of buckets of water at the same time, and the process does not take time.
  • The piglet must have a minute to die cooling time after drinking water. During this time, you can only observe, not continue to feed pigs.
    After minutes to die, all the pigs that drank the poison will die and all the other pigs will survive.
    Repeat this process until time runs out.
    Give you the number of buckets, minutestodie and minutestotest, and return the minimum number of pigs required to determine which bucket is toxic within a specified time.

Solution

The optimal solution is that all pigs are numbered according to a decimal number to get a number, and each pig can determine a digit of this number.
How do I find this decimal number?
Obviously, our \ (number of pigs + 1 \) is our base. Then we can get the maximum liquid quantity in the range of \ (ANS \ Le base ^ {CNT} \)
therefore

cnt = minutesToTest / minutesToDie
ans = ceil(log(buckets) / log(base));

AC_CODE

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