带毒的水

　　　　　　　　　　　　　　　　　　　　带毒的水

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;
    }

View Code

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

 

原文链接:https://www.cnblogs.com/gznb/p/11206098.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有