Binary search
bh1234666
·
·
题解
看到这题第一反应可能是贪心，二分时每次使区间最小，但是这样做是不正确的。因为直接贪心时靠前的操作权值^*小，靠后的操作权值大，靠前的决策会影响靠后的决策，即权值小的决策影响权值大的决策，显然不正确。
例如对于 $n=13$,查询序列的第 $5$ 个（下标为 $4$，接下来的位置均指下标）。直接贪心过程为：
$$
[0,12] \stackrel{w=1}{\longrightarrow} [0,5] \stackrel{w=0}{\longrightarrow} [3,5] \stackrel{w=1}{\longrightarrow} [4,5] \stackrel{w=0}{\longrightarrow} [4,4]
$$
但实际上有更优解法：
$$
[0,12] \stackrel{w=0}{\longrightarrow} [0,6]\stackrel{w=0}{\longrightarrow}[4,6] \stackrel{w=1}{\longrightarrow} [4,4]
$$
第一步贪心看似比最优解短了 $1$ ,贪心的下一步使得查找的值出现在了中部，导致 $ [3,5] \stackrel{w=1}{\longrightarrow} [4,5]$ 这一步无法使得长度折半。而贪心前面短的那一步最优解在下一步除二时除掉了，而在更靠后的 $[4,6] \stackrel{w=1}{\longrightarrow} [4,4]$ 比贪心短了 $1$。
对于 $\text{sub2}$ ，发现每次 $w$ 的值不会影响答案，直接输出 $\log_2 n$ 即可。
发现询问次数只有 $100$ 次，直接暴力。为便于实现，可以采用递归实现的二分，每次递归时分两类递归取最小即可。
由于递归层数为 $\log_2 n$ 层，每层分两种情况，最终复杂度为 $O(nq)$，可以通过此题。
核心代码：
```
int find(int k,int f,int l)
{
if(f==l) return 0;
int mid=(f+l)>>1,ret=32;
if(mid<k) ret=find(k,mid+1,l);
else ret=find(k,f,mid);
mid=(f+l+1)>>1;
if(mid<=k) ret=min(ret,find(k,mid,l));
else ret=min(ret,find(k,f,mid-1));
return ret+1;
}
int main()
{
int i,n,q,k;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",num+i);
scanf("%d",&q);
while(q--)
{
scanf("%d",&k);
for(i=0;i<n;i++)
if(num[i]==k) break;
printf("%d\n",find(i,0,n-1));
}
return 0;
}
```