# leetcode-458-Poor Pigs

### 题目描述：

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.

### 要完成的函数：

int poorPigs(int buckets, int minutesToDie, int minutesToTest)

### 说明：

1、这其实是一道数学题，想明白了代码不超过两行。我不会说我连前面的1000个桶这道具体的题目都做错的……直到看见答案才明白过来。

2、具体数字的题目，答案是5，不是8、也不是23、更不是250。具体解法如下：

0min

15min

30min

45min

60min

0min

×

×

×

×

×

15min

×

×

×

×

×

30min

×

×

×

×

×

45min

×

×

×

×

×

60min

×

×

×

×

×

3、所以放到通用的题目里面，n个待判定的水桶，限时p分钟，m分钟出一次结果，这道题结果就是ceil(log(p/m+1)n)，ceil是取上限函数。

```    int poorPigs(int buckets, int minutesToDie, int minutesToTest)
{
int chances=floor(minutesToTest/minutesToDie);
return ceil(log10(buckets)/log10(chances+1));//变换一下底数，以10为底，结果一样
}```

205 篇文章43 人订阅

0 条评论

## 相关文章

281100

42170

46990

### 图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆，要求有2个： 这 n 个城市的任意两个之间都可以通信； 铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，...

1.1K70

35360

27040

35460

13560

### HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...

35870

35160