带毒的水

青旅半醒 2021-11-10 02:40 206阅读 0赞

# 　　　　　　　　　　　　　　　　　　　　带毒的水 #

### 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.

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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  函数。

转载于:https://www.cnblogs.com/gznb/p/11206098.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/d68dbe73bf1941ffacc08cc6128c0d44.png