qq_44684286的博客

原创 二分解决瓶中毒药问题

这是一道微软面试题题目：分析：假设不管毒药和水混合，不管毒药浓度为多少，小鼠喝过就会死。现进行这样的实验（原理二分法）：1000瓶水，先将前500的混合，让一只小鼠喝。如果死亡，则前500有毒药，后500瓶直接排除；若不死亡，则后500瓶有毒药。最后二分结束的条件是begin = end 这是直接输出begin即毒药的标签号。问题的时间复杂度O(nlogn), 空间复杂度O(1)。解答：#include <iostream>#include <vector>u