Daily C/C++ 可怜的小猪

Daily C/C++ 可怜的小猪

今天这个文章思路来源于leetcode的每日一题

题目链接

万能的网友们给出了各种各样的解题方法，这里我也提两种我认为比较有意思的方法

首先一个通用的前提是，我们对于题目中给出的时间限制，我们可以令stage = ceil(minToTest / minToDie)

即我们一共有stage轮操作的机会

这里，我们将bucket个桶分成一个k维的超立方体，或者是一个k维的矩阵。他们的长度都是stage + 1

因为每个小猪在每一轮都有可能死掉，所以一个小猪在stage轮中的状态为第一轮死，第二轮死...，第stage轮死，没死

一共是stage + 1种状态

对于这bucket个桶，其中一个是有毒的，我们刚才已经把它分成了k维的超立方体，那么我们想要找到这个有毒的桶实际上是在这个超立方体中确定一个坐标

这个坐标为(x1, x2, ..., xk)

由于我们刚才限定了立方体的长度是stage + 1,所以x的取值个数也就是stage + 1

对于每头小猪来说，他们都负责这k维中的其中一维，他们负责确认有毒桶在他们负责的这一维的坐标是多少

比如第i只小猪，就负责确认xi是多少。我们用k只小猪就可以确认这个有毒桶的具体坐标

每只小猪在每一轮都可以喝掉一个k-1维的超平面中所有桶的水，以此来确定有毒的桶是不是在这个超平面上

具体一点，比如k=3

我们将桶组织成了一个立方体的结构，那么每只小猪每次就可以喝掉一个平面中的所有水，如果他这一轮死掉了，说明毒桶就在这个平面中。

同样的道理，其他两个的小猪也可以确定两个平面。那么最终这三个平面的那个交点就是桶的位置

我们希望猪的数量最小，那么也就是k尽可能的小

根据刚才的推导，可以发现我们要满足的条件是(stage + 1) ^ k >= bucket

两边同取log以后，得到的公式就是k * log(stage + 1) >= log(bucket)

这样我们就可以找到k的最小值

第二种方法就是信息论的方法

我们知道信息熵的公式是

其实对于这个公式的一个简单情况，当所有概率都相同的时候，我们带入公式得到的值是log(m)

其中m表示状态数

这个值还有另一种解释，就是信息量

等概率的存在m个状态，他的信息量就是log(m)

对于我们这道题，每个小猪的状态就是stage + 1，那么每只小猪所承载的信息量就是log(stage + 1)

对于bucket个桶，我们有bucket种不同的状态，因为毒桶可以是任何一个桶。那么这些桶所承载的信息量就是log(bucket)

我们需要用k个小猪，那么一共就有k * log(stage + 1)这么多的信息量，我们要确认的是log(bucket)

当我们含有的信息量大于我们要确认的信息时，我们就有方法可以实现

所以我们要满足k * log(stage + 1) >= log(bucket)

和上面推导出来的公式一样，但是更加简洁