一开始的想法如下：
就是利用二分法，对于一个区间\([l,r]\)，分成\([l,mid-1],[mid,r-1]\)两部分，各找两个朋友喝，右边还空出一个\(r\)，如果前面两个朋友都没中毒，那说明\(r\)这瓶有毒。
但仔细一想，我们发现\([1,n)\)的瓶子中任意一个我们分出的区间\([l,r]\)，都用去了\(r-l+1\)个朋友。比如上图中\([4,7]\)区间，就用了\(4\)个朋友。所以我们最终只是省下了\(1\)个朋友，用去了\(n-1\)个朋友。
这显然不够优，我们应该怎么分配呢？
你可能以前玩过一个猜数字的游戏：给你\(6\)张卡片，问你想的数在哪些卡片上。最终就可以猜出你想的数。
这个游戏的原理就是第\(i\)张卡片上的数字，都是二进制表示中第\(i\)为\(1\)的数字。最终你选了哪些卡片，就说明你选的数二进制表示中哪些位上是\(1\)。
我们用同样的原理，让第\(i\)个朋友去喝二进制表示中第\(i\)为是\(1\)的果汁。最终我们只需要用\(\lfloor \log_2(n-1)\rfloor+1\)个朋友。
之所以是\(n-1\)，是因为我们可以把最后一瓶空出来，如果所有朋友都没中毒，说明毒就下在最后一瓶里。所以我们需要特判，如果最终结果为\(0\)，则输出\(n\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
map<int,set<int>> ma;
string s;
int main(){
cin>>n;
int m=__lg(n-1)+1;
cout<<m<<endl;
for(int i=1;i<n;i++){
int tmp=i;
for(int j=1;tmp;j++){
if(tmp&1) ma[j].insert(i);
tmp>>=1;
}
}
for(auto i:ma){
cout<<i.second.size()<<" ";
for(auto j:i.second) cout<<j<<" ";
cout<<endl;
}
cin>>s;
s=' '+s;
int ans=0;
for(int i=m;i>=1;i--){
ans<<=1;
if(s[i]=='1') ans|=1;
}
cout<<(ans==0?n:ans)<<endl;
return 0;
}