自动搬运

查看原文

来自洛谷，原作者为

	bh1234666 这蒟蒻很烂，什么都没有留下

搬运于2025-08-24 22:39:27，当前版本为作者最后更新于2022-05-01 11:00:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到这题第一反应可能是贪心，二分时每次使区间最小，但是这样做是不正确的。因为直接贪心时靠前的操作权值$^*$小，靠后的操作权值大，靠前的决策会影响靠后的决策，即权值小的决策影响权值大的决策，显然不正确。

$^*$ 此处权值定义较复杂，可以简单理解为对后续长度产生影响（缩短 $1$）的概率。

例如对于 $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;
}