2022-08-26 12:34:22
题意分析
不难看出，这道题是一个对于二分查找中 \(mid\), \(l\), \(r\) 如何取值使得总查询次数最少问题。
这个 \(w\) 是影响最终结果的决定性因素，而它的取值只可能是 \(0\) 或 \(1\)。
当时在考场上瑟瑟发抖的我第一时间想到能不能使用深搜，感觉复杂度很高（排除了正解），就暂时没有去打，而是被 \(Task\) \(2\) 的 \(n=2^k\) 深深吸引了。显然当 \(n\) 满足该条件时，我们只需要按正常的二分去统计查询次数就好了，于是我得到了 \(35\) 分。
就在我第三题迟迟构造不出来时，我想到回来打深搜了。
思路
那么问题来了，怎么搜？
在上文中我讲到， \(w\) 只有两种取值 \(0\) 或 \(1\)，那么我们其实就只用去考虑当 \(w\) 分别取这两个值时， \(mid\), \(l\), \(r\) 如何去取即可。
直接讲，讲不清，那我们结合代码一起看吧。
Code
void dfs(int l,int r,int g){// g是循环的次数
if(l>=r){
ans=min(ans,g); //达到二分所需条件就更新
return;
}
ll mid1=(l+r)/2,mid2=(l+r+1)/2;//mid1是当w=0时的情况,mid2是当w=1时的情况
if(g>=ans)return; //显然当w=0时，就和正常二分一样
if(a[mid1]>=key){
dfs(l,mid1,g+1);
}else{
dfs(mid1+1,r,g+1);
}
if(a[mid2]-1>=key){ //第二种情况我们可以在题面中找到构造的方法
dfs(l,mid2-1,g+1); //题面中的 mid-w,所以这里要减一
}else{
dfs(mid2,r,g+1);//这里同理
}
return;
}
剩余部分就直接调用函数即可，但是要注意 \(ans\) 的初值。
最后看见一片绿的我才发现搜索是正解。