#P8481. 「HGOI-1」Binary search

    ID: 7537 远端评测题 1000ms 64MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>二分洛谷原创O2优化深度优先搜索,DFS洛谷月赛

「HGOI-1」Binary search

题目背景

bh1234666\text{bh1234666} 正在学习二分查找

题目描述

众所周知二分查找的 mid\text{mid} 在计算时可以取 l+r2\lfloor\dfrac{l+r}{2}\rfloor 或者 l+r2\lceil\dfrac{l+r}{2}\rceil,于是有选择困难症的 bh1234666\text{bh1234666} 同学在自己的二分查找代码中加入了随机化,每次随机选取其中的一个作为 mid\textit{mid}

注意,选取不同的 mid 其他参数也会受到影响,请以代码为准。

现在 bh1234666\text{bh1234666} 给你了二分查找使用的序列(保证为单调递增)以及他想要寻找的数(保证在序列内),他想知道在运气最好的情况下循环需要进行几次(即代码中 cnt\textit{cnt} 的可能的最终值的最小值)。

循环:

int find(int *num,int x,int len)
{
	int l=0,r=len-1,mid,cnt=0,w;
	while(l<r)
	{
		cnt++;
		w=rand()%2;
		mid=(l+r+w)/2;
		if(num[mid]-w<x) l=mid+!w;
		else r=mid-w;
	}
	return mid;
}

递归:

int cnt;
int get(int *num,int x,int l,int r)
{
	if(l==r) return l;
	cnt++;
	int w=rand()%2;
	int mid=(l+r+w)/2;
	if(num[mid]-w<x) return get(num,x,mid+!w,r);
	else return get(num,x,l,mid-w);
}
int find(int *num,int x,int len)
{
	cnt=0;
	return get(num,x,0,len-1);
}

注:以上两代码完全等价。

在此对上述代码中的 ww 的作用做进一步阐释。

例如对于区间 [0,7][0,7],有 88 个成员。虽然 midmid 的取值会因为 ww 的取值改变而改变,但是最终确定的区间一定是 [0,3][0,3][4,7][4,7],选手可以就上述代码自行模拟。

对于区间 [0,6][0,6],有 77 个成员。mid\textit{mid} 的取值与 ww 的取值无关,但是 llrr 的取值会受到 ww 的影响,最终确定的区间可能是 [0,2][0,2][3,6][3,6]w=1w=1)或 [0,3][0,3][4,6][4,6]w=0w=0)。

输入格式

第一行给出一个整数 nn 表示序列长度。

第二行给出单调递增的 nn 个整数表示 bh1234666\text{bh1234666} 的序列。

第三行一个整数 qq 表示询问的次数。

接下来 qq 行每行一个整数表示需要查询的数字。

输出格式

对于每个询问回答一个整数,表示最小的循环次数。

10
1 2 4 6 7 8 10 13 15 17
3
4
10
15
3
3
3
13
1 2 4 6 10 12 19 23 45 99 101 123 134
5
1
2
10
19
123

3
4
3
3
4

提示

样例 1 解释

44

[1,5][1,5]

[1,3][1,3]

[3,3][3,3](退出循环)。

样例 2 解释

查询 1010 的位置。

$$[1,13] \stackrel{w=0}{\longrightarrow} [1,7]\stackrel{w=0}{\longrightarrow}[5,7] \stackrel{w=1}{\longrightarrow} [5,5] $$

数据范围及约定

本题采用捆绑测试,共有 33subtask\text{subtask},最终分数为所有 subtask\text{subtask} 分数之和。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \text{特殊限制} \cr\hline 1 & 25 & n \le 20 \cr\hline 2 & 35 & n=2^k(k \in \mathbf{N}) \cr\hline 3 & 40 & \cr\hline \end{array} $$

对于 100%100\% 的数据,保证 1n2201 \le n \le 2^{20}1q1001 \le q \le 1001numi1091 \le num_i \le 10^9

本题有 extra sub