欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

带毒的水

程序员文章站 2022-07-05 08:50:19
带毒的水 Problem Description 有N瓶水,其中只有一瓶有毒,小白鼠只要喝了一点带毒的水24小时 内就会死亡,问至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒。 Input 每行一个整数,表示水的瓶数 Output 每行一个整数,表示至少需要小白鼠的数量 Sample Input ......

                    带毒的水

problem description

有n瓶水,其中只有一瓶有毒,小白鼠只要喝了一点带毒的水24小时 内就会死亡,问至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒。

input

每行一个整数,表示水的瓶数

output

每行一个整数,表示至少需要小白鼠的数量

sample input

2
3

sample output

1
2

解释:

因为这种毒药的发作需要24个小时,题目要求在24小时之类可以检测出来,所以应该要多只老鼠同时喝,对于这种毒药,只需要一滴就可以让老鼠死,所以不需要整瓶整瓶的喝,喝一滴就好,因此一只老鼠可以同时品尝几杯水,对于喝过水的老师的状态,我们就只有两种情况,死或者是不死。把每一个老鼠看做是一个二进制位,那么两只老鼠就是的情况就是:

{{0 0}, {0 1},  {1 0}, {1 1}},假设四瓶水分别是abcd,第一只老鼠喝了ab,第二只喝了bc。那么

0 0 = d,      0 1 = c, 1 0 = a, 1 1  = b

现在假设有8瓶水,分别是

000 = 0

001 = 1

010 = 2

011 = 3

 ....

111 = 7

将其转置一下:

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

 

0 1 2 3 4 5 6 7

那么还是以abcd efgh为例

第一只老鼠喝了 efgh

第二只老鼠喝了 cdgh

第三只老鼠喝了 bdfh

所以就可以看出,一个问题,2瓶水1个老鼠,4瓶水两个老鼠,8瓶水三个老鼠。反过来想一下8瓶水只要3个老鼠,两只老鼠只能解决4瓶水,那5, 6, 7瓶水,肯定是要3只老鼠的。

因此这么一分析,我们就知道,答案就是 2^x >= n  所以,我们只要找到第一次满足这个等式的x.

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int main(){
        int n;
        while(cin >> n){
            int x = 1;
            int t = 0;
            while(n > x){
                x = x << 1;
                t++;
            }
            cout << t << endl;
        }
        return 0;
    }

个人觉得位运算天下第一,不过这个题也可以用<math.h>库里面的,log  函数。