Leetcode458.Poor Pigs可怜的小猪
2024-08-26 09:06:18
有1000只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在15分钟内死去。
问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?
回答这个问题,并为下列的进阶问题编写一个通用算法。
进阶:
假设有 n 只水桶,猪饮水中毒后会在 m 分钟内死亡,你需要多少猪(x)就能在 p 分钟内找出“有毒”水桶?n只水桶里有且仅有一只有毒的桶。
一次喝一个桶的,15分钟后没挂再喝第二桶,一小时60分钟内可以喝 60/15 = 4 次,如果有5桶水,那个只要喝前4桶就只能第5桶是否有毒。一只能验5桶,2只猪应该可以验5*5桶(一只负责行一只负责列)
class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
if(buckets <= 1)
return 0;
int k = (minutesToTest / minutesToDie) + 1;
int cnt = 1;
while(cnt <= buckets)
{
if(pow(k, cnt) >= buckets)
return cnt;
cnt++;
}
return 0;
}
};
最新文章
- 从头开始构建LINUX[内核更新和资料]
- spark standalone ha spark submit
- 移除IIS默认的响应头(转载)
- APPLICATION ERROR #1502 .
- 百度地图API示例之添加/删除工具条、比例尺控件
- 对div作用域的理解
- UIFont 设置字体
- Tengine:基于Nginx的衍生版
- ExtJs 4.2.1 点击按钮弹出表单的窗口
- Java面试求职之==与equals()差别
- 在html页头设置不缓存
- 常用数据结构及复杂度 array、LinkedList、List、Stack、Queue、Dictionary、SortedDictionary、HashSet、SortedSet
- javascript和css浏览器兼容性总结
- 所有事件event集锦
- 【2】构建一个SSM项目结构
- php 使用str_replace替换关键词(兼容字符串,一维数组,多维数组)
- Hive Shell 命令详解
- canal 入门
- 【记录】css样式
- Django:提交表单时遇到403错误:CSRF verification failed
热门文章
- wpf 定时器应用,在界面动态刷新时间
- 2019-9-23-asp-dotnet-core-3.0-接口返回-json-使用-PascalCase-格式
- scull 中的设备注册
- 【期望DP】[zoj3329]One Person Game
- openSUSE安装Composer
- leetcode-122-买卖股票的最佳时机②
- 17多校6 HDU - 6102
- SPOJ 1043 GSS1 - Can you answer these queries I
- 19-11-08-Night
- C#多线程实现方法——线程池(Thread Pool)