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.
N个桶,一只猪喝了会在minutesToDie分钟内死亡,你有minutesToTest分钟的时间,求最少要多少猪试出毒药
如果有4个桶,15分钟死亡,有15分钟的时间,用二进制对桶编号
00 01 10 11
__ _A B_ BA
0表示没喝
1表示喝了
_表示没喝 如果A挂了,B没挂,则是01桶 最少要2只猪
如果有8个桶,15分钟死亡,有30分钟的时间,用3进制对桶编号,并且有2轮测试
0表示两轮都不喝
1表示第一轮喝,第二轮不喝
2表示第一轮不喝,第二轮喝
最后推出公式为(测试次数+1)^x >= 桶数 求x的最小整数值
C++(2ms):
class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
return ceil(log(buckets)/log(minutesToTest/minutesToDie +)) ;
}
};
最新文章
- (转)Should 断言的基本使用方法
- Plyr – 简单,灵活的 HTML5 媒体播放器
- 认识与学习 BASH
- Another 20 Docs and Guides for Front-End Developers
- 【二分】【最长上升子序列】HDU 5489 Removed Interval (2015 ACM/ICPC Asia Regional Hefei Online)
- java遍历泛型的方法
- ant的入门 配置与安装
- js 拖拽实现
- AngularJs学习笔记0——前言
- makefile中";:=";,";=";,";?=";,";+="; 之间的区别
- java游戏开发杂谈 - java编程怎么学
- 分享几个常见的CMD命令,可能会用的上
- 最新亚马逊 Coupons 功能设置教程完整攻略!
- LeetCode--035--搜索插入位置(java)
- Nginx的编译安装及选项
- SAP S/4 HANA 1709 Fully Activated Appliance
- java 编程思想
- mongodb内建角色
- django模板总结
- 多目标跟踪MOT评价指标