马克思智慧么？

每只老鼠根据它的编号去到相应的位数，如果有1就喝那瓶药，比如说上面这个表里面10号鼠喝1号、3号，9号鼠喝2号、3号。第一只鼠喝的次数最多：1+2+16+32+64+128+256+1=500
如果你说的二分法指的是这个，那么我没有异议。如果你说的是二分查找，那我真不知道怎么解。我所知的二分查找：一串定序的数字，寻找某一个数字是否在其中，如果在，得到它的位置。我觉得这个问题和二分查找没有任何联系，也有可能是我见识浅薄。希望你能告诉我你是怎么用二分查找解的。

[-] malabax253 | 1 points | Jan 18 2022 03:30:23

刚才有个浪友告诉我怎么用二分法做了，是我思维狭隘了，多谢。

[-] yauvver | 1 points | Jan 18 2022 04:15:39

两个本质是一样的

一个是自顶向下，一个是自下而上

[-] CuriousSavings1088 | 1 points | Jan 18 2022 02:09:01

都让你懂完了

[-] LIBrezhnev | 1 points | Jan 18 2022 02:32:41

类似海明码的纠错过程吧

[-] TwistSubstantial9215 | 1 points | Jan 18 2022 01:30:38

二分法都不懂的话可以去死了

[-] TomDiao | 1 points | Jan 17 2022 19:03:56

binary/bisection search 推特看过这截图了

[-] malabax253 | 1 points | Jan 18 2022 01:58:47

我很好奇你怎么用二分查找来解决这个问题

[-] TomDiao | 1 points | Jan 18 2022 03:07:21

每次把矿泉水分半（500/500），每一半把水混合各喂一只老鼠，有老鼠挂掉的那一半继续重复同样的动作，到最后10只老鼠足够查找出有毒液的那一瓶（250/250）（125/125）（63/62）（31/31）（15/16）（8/8）（4/4）（2/2）（1/1）

[-] malabax253 | 1 points | Jan 18 2022 04:07:22

牛逼，懂了

[-] xxxMilfHunter6969xxx | 1 points | Jan 17 2022 23:39:16

利用同样的思路我提供一个不是二分法的解法。把1000个瓶子用二进制标号，第一瓶是0000000001，取出液体喂给第一只白鼠，第五瓶则是0000000101，取出液体喂给第一只和第三只，以此类推，最终根据死掉的白鼠的位置可以得到一个二进制数，转成十进制就是毒药瓶的编号。

[-] remember8964 | 1 points | Jan 18 2022 00:26:20

这个思路有时候叫bitmap，利用比特数标定位置

[-] Xcaret17 | 1 points | Jan 18 2022 00:51:58

这个是正解，甚至用高中知识都能解释明白。

[-] jiangjindong | 1 points | Jan 18 2022 01:14:10

要么二进制坐标，要么简单的二分法十分法，把几百份几百份这勾兑查找，第一个方法最好，第二个方法毒药如果被稀释有可能导致效果不佳

[-] IntroductionOk7106 | 1 points | Jan 18 2022 04:54:06

就算要防止稀释，这种二进制做表法还不如遍历法。一只🐁从头喝到尾，到哪瓶喝死了哪瓶就是毒药。这样总共需要喂的次数还比比二进制要少。

[-] jiangjindong | 1 points | Jan 18 2022 10:51:13

遍历法关键是毒药生效如果需要时间，比如一个小时生效，就要1000小时

[-] IntroductionOk7106 | 1 points | Jan 19 2022 23:03:25

什么事后诸葛亮

[-] beatit_zxz | 1 points | Jan 18 2022 02:04:13

牛逼虽然不懂计算机但这显然比二分法自作聪明的憨批强多了本生化环材废物第一反应就是稀释了鲨不掉鼠鼠

[-] IntroductionOk7106 | 1 points | Jan 18 2022 04:50:17

看似有趣但其实这样还不如让一只🐁一路喝到最后。如果目的是找出有毒的瓶子，编码本身没有任何意义，因为当第一只🐁死亡后就已经能找出毒药瓶了，继续寻找后续9位数是没有必要的。

[-] Quantum_convolution | 1 points | Jan 18 2022 04:59:37

即使考虑稀释对毒性的影响，“二分法”仍然是最快速解法，如果小鼠没被毒死那么也继续分组、测试，此时的分组形成一颗二叉树，当小鼠被毒死时抛弃树中其它分支，只对有毒分支继续分组测试即可。比如说毒药起效的浓度阈值在一百倍稀释，那我们在二叉树的第三层即可发现有毒分支，此时总样本数只有八个。

[-] Quantum_convolution | 1 points | Jan 18 2022 05:07:54

我也同意实操里不会有人这么干的说法，不过数学题的语境和实际当然是不一样的😋楼上的bitmap方法很巧妙，不过缺点就是在毒药浓度阈值较低的情况下时间复杂度比“二分法”高太多

[-] liveybraen | 1 points | Jan 18 2022 06:18:14

以前的面试题真简单啊，现在不整个拓扑排序cached dfs都不好意思和人打招呼

[-] Marquez89 | 1 points | Jan 17 2022 17:30:54

二分查找，可能是少儿编程题

[-] Adept-Orchid1181 | 1 points | Jan 17 2022 18:07:03

什么NOIP普及组

[-] Wonderful-Event3796 | 1 points | Jan 17 2022 18:14:35

政治面前讲科学，反革命了属于是

[-] packWolf77 | 1 points | Jan 17 2022 17:32:36

不是，这种屁股都能想明白的问题，出题的hr不会沾沾自喜吧？

[-] ellipsedy | 1 points | Jan 17 2022 17:33:26

俺寻思试管无限量一只鼠鼠不就够了

[-] furry199564 | 1 points | Jan 17 2022 18:51:29

你是想撑死鼠鼠嘛？

[-] 6324fans | 1 points | Jan 17 2022 23:04:45

他这个才是正确答案。二分法的话第一只老鼠也要喝500瓶的混合。

[-] Key-Mud-6810 | 1 points | Jan 17 2022 19:50:58

我也想说，然后给其它9只发个红袖章当监督员！

[-] W4ULFiLZ | 1 points | Jan 17 2022 17:45:28

Too easy to be Microsoft

[-] Jacuening | 1 points | Jan 17 2022 17:47:14

典

[-] Potential_Grape_2877 | 1 points | Jan 17 2022 18:09:56

Too easy to be Communist

[-] GJT11kazemasin | 1 points | Jan 17 2022 18:24:52

谔谔，没学过CS真的会把它当成脑筋急转弯，原来是二分法

[-] cprwwww | 1 points | Jan 17 2022 18:39:22

我感觉学过小学数学就应该有类似思路了

[-] wep0523z | 1 points | Jan 17 2022 19:03:41

都他妈base 2你们是想杀多少🐀🐀

[-] cheshire_cat_2022 | 1 points | Jan 17 2022 19:28:32

这明明是二进制，是个几把的二分法？楼上这么多伪cs的吗

[-] Pleasant_Corgi_877 | 1 points | Jan 17 2022 19:57:25

这有一个前提，是毒药无论稀释多少倍都还有效

[-] Ubuntu_20_04_LTS | 1 points | Jan 17 2022 20:20:30

leetcode poor pigs

[-] chonglang_guanjun | 1 points | Jan 17 2022 20:50:31

14億

[-] Ubuntu_20_04_LTS | 1 points | Jan 17 2022 21:10:07

教员您回来了！

[-] sodomfarm | 1 points | Jan 18 2022 02:52:35

找1000頭支那豬每頭發一瓶跟它們說參與實驗，喝完以後轉綠碼或者給一桶泡麵，分成10列，每列100人，天網監控都安排上，打鈴後準時喝，15分鐘後出結果，倒下的人刨去營養不良的就是中毒的，不放心還可以請法醫劉仲敬現場化驗。此方法又能準確的找出毒藥，還能在1小時內出結果，成本只有一頭支那豬。

[-] C_P_Y | 1 points | Jan 18 2022 10:06:57

成本只有一頭支那豬...

哭啊所以到頭來連泡麵也沒發綠碼也沒轉

:D

[-] Ubuntu_20_04_LTS | 1 points | Jan 18 2022 14:01:45

才一头，大佐会认为你过于节省成本了

[-] BernesiaMons | 1 points | Jan 18 2022 05:36:28

一小时内最多次数为四次（不计操作时间和其他时间）为2的四次方，即1000/16 = 62.5. 63只蜘蛛同时从16开始二分，4次都得出结果

[-] Ubuntu_20_04_LTS | 1 points | Jan 18 2022 13:56:27

题目打字仓促，有些地方没说清楚，说明一下有这些条件：1. 就像你说的操作时间和其他时间不计 2. 蜘蛛一次可以喝下任意多的试管溶液，就是一头蜘蛛一次试几瓶都可以 3. 应该问一共需要几头蜘蛛（不管试验完毕死的活的）

[-] fengkuangyvzhouew | 1 points | Jan 17 2022 20:23:27

给空试管干嘛？直接让老鼠喝不就行了吗

[-] Trick_Purchase5662 | 1 points | Jan 17 2022 20:34:32

每瓶倒1支试管，倒1000支试管，让一只小白鼠一支试管一支试管的试毒。其他小白鼠给他鼓劲

[-] ImpossibleTech | 1 points | Jan 17 2022 21:16:22

绷，九个领导是吧……

[-] Fanbizheng | 1 points | Jan 17 2022 22:47:01

除非设置每只小白鼠只能被喂一次或者限定时间，不然不需要二进制吧。

[-] Odd-Acanthocephala63 | 1 points | Jan 18 2022 08:35:22

題目敘述不完整

[-] UltraUnderpants | 1 points | Jan 17 2022 23:12:04

第一轮，1000瓶水，10鼠。每一百瓶水取样装一试管，老鼠喝。

第二轮，100瓶水，9鼠。每11瓶取样装一试管，老鼠喝。

第三轮，老鼠都活着，毒药找到了是轮空的那瓶。老鼠死了，那就11瓶水，8鼠。

第四轮，一鼠一瓶，死了就找到毒药了，没死再来一轮。

每轮取模运算，水/鼠，记录商和余数

水样组和轮空组，哪组死鼠了就当做新的被除数，更新鼠数

商不为1就继续，商为1就return index

[-] Available-Pain7749 | 1 points | Jan 18 2022 02:29:50

我也是这个思路

[-] Aggressive_Demand_49 | 1 points | Jan 17 2022 23:22:22

这不是典图吗，楼上怎么还一本正经分析起来了

[-] Interesting-Fall-928 | 1 points | Jan 18 2022 02:41:24

一看见题小黄人的做题癖就发作了

[-] shazhi001 | 1 points | Jan 18 2022 00:09:22

自己喝完一千瓶重开

[-] tuzhixuePhd | 1 points | Jan 18 2022 00:23:26

无数个干净试管，一平一滴的挨个儿试不就完了？二分个几把毛呢

[-] [deleted] | 1 points | Jan 18 2022 07:13:44

[removed]

[-] lrofocale | 1 points | Jan 18 2022 00:53:37

信息论

[-] LengthinessNo2934 | 1 points | Jan 18 2022 01:22:32

二分法？

[-] biewenwoshishei | 1 points | Jan 18 2022 02:39:54

建个笼子把十只鼠关起来渴死也不让他们喝水然后宣布我们已经成功解决了水中的毒素实现了鼠鼠零中毒率

[-] minisherry | 1 points | Jan 18 2022 03:08:50

这题本来是想问二分查找？

[-] XiE2021 | 1 points | Jan 18 2022 03:40:07

什么平子与鼠鼠的故事

[-] Echooooox | 1 points | Jan 18 2022 03:43:23

这道题还用问？有毒的那个肯定是洗净瓶

[-] North_Ad4316 | 1 points | Jan 18 2022 04:04:05

我認為分成十組一組一百個混合分別餵給十隻老鼠，中毒的那組再分成十組一組十個先出九組給九隻老鼠餵，如果都沒中毒就是剩下的那組十個有毒，如果有中毒的就從那一組十個再分出來餵，這樣應該很快就確認完了

[-] No-Hunt-4486 | 1 points | Jan 18 2022 04:04:20

我就比较粗糙，给🐀摁喝水，喝出问题就是那一瓶。10个🐀，10个线程

[-] UNI_C | 1 points | Jan 18 2022 04:40:30

钓鱼帖钓起了无数冲浪做题家。

[-] 3b1b | 1 points | Jan 18 2022 05:13:51

做题也是为了润嘛

[-] 3b1b | 1 points | Jan 18 2022 05:12:01

什么汉明码

[-] ChinaNo_233 | 1 points | Jan 18 2022 05:54:07

自己一瓶一瓶喝边喝边读腊选可以有效防止毒药发作

[-] cnmgcd1314 | 1 points | Jan 18 2022 09:21:39

每瓶放一滴到试管里让老鼠舔，只有一瓶有毒，那老鼠死了不就试出来了么？是我没看懂题目么？

[-] LeDsi | 1 points | Jan 18 2022 13:16:12

又沒限定每隻鼠鼠只能喝一次，喝水又不會死，一瓶一瓶喝，喝到死不就知道了，逮著一隻硬喝1000瓶也行，但是十隻一起上玩俄羅斯輪盤更刺激

[-] FreeHK_Now_Ray | 1 points | Jan 18 2022 14:06:20

明明有10只老鼠，為何要用二分法？直接每次分剩下老鼠數+1不就好了？第一次分成10份90支和1分99支，每只老鼠喝90支的混合，那只死了就是那一份有毒，都沒死就是最得一份。第一次就能剩下90/99支，第二次剩9支，第三次就能找出毒藥了，還有機會一只老鼠都不用死.........

[-] like11115 | 1 points | Jan 18 2022 17:00:43

分你媽個逼，沒限時我一天10隻老鼠各試一瓶不就好了，低能問題，可憐傳統華人思想權威崇拜，說個機掰微軟面試、馬雲面試之類的就一堆人高潮

[-] Vast_Spite8928 | 1 points | Jan 18 2022 21:30:56

浪人不会都学cs把

[-] ianian676 | 1 points | Jan 19 2022 01:56:35

做题家