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。具体解法如下:

假设有25个桶,我们只需要两只猪。把25个桶放成5行5列,如下形状:每个×代表一个水桶。

0min

15min

30min

45min

60min

0min

×

×

×

×

×

15min

×

×

×

×

×

30min

×

×

×

×

×

45min

×

×

×

×

×

60min

×

×

×

×

×

第一只猪在0min喝下第一行的水,在15min喝下第二行的水,在30min喝下第三行的水,在45min喝下第四行的水。如果45min喝下60min出结果的时候,猪还没say goodbye的话,那么毒必定在最后一行。

与此同时,第二只猪在0min喝下第一列的水,15min喝下第二列的水……类推。如果45min喝下60min出结果的时候,猪还在,那说明毒在最后一列。结合第一只猪的结果,说明毒在最后一行最后一列。

我们可以看出,一只猪可以判断一个维度的信息,两只猪可以决定两个维度的信息,也就是5^2=25个水桶的情况可以由两只猪判断得出。

所以三只猪可以判断5^3=125,四只猪可以判断5^4=625,五只猪可以判断5^5>1000个水桶的情况。

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为底,结果一样
    }

上述代码实测2ms,beats 100% of cpp submissions。大家做的都一样。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2080 夹角有多大II

夹角有多大II Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

281100
来自专栏数据结构与算法

2017.9.17校内noip模拟赛解题报告

预计分数:100+60+60=220 实际分数:100+60+40=200 除了暴力什么都不会的我。。。。。 T1 2017.9.17巧克力棒(chocolat...

42170
来自专栏开发与安全

算法:图解最小生成树之普里姆(Prim)算法

我们在图的定义中说过,带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就...

46990
来自专栏算法channel

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

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

1.1K70
来自专栏数据结构与算法

洛谷P3209 [HNOI2010]PLANAR(2-SAT)

题目描述 若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交,则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要...

35360
来自专栏数据结构与算法

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

27040
来自专栏算法修养

整数划分总结

整数划分问题: 笼统上说就是将一根整数划分成若干个整数之和的方案数。整数划分很多不同的问法,也有隐晦的问法。比如n个苹果放到m个盘子里,比如n个砖块堆成m个...

35460
来自专栏逍遥剑客的游戏开发

玻璃效果

13560
来自专栏数据结构与算法

HDU 3078 Network

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

35870
来自专栏Python爬虫与算法进阶

萌新刷题(十三)买卖股票的最佳时机

题目 假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例...

35160

扫码关注云+社区

领取腾讯云代金券