#P8481. 「HGOI-1」Binary search
「HGOI-1」Binary search
题目背景
正在学习二分查找。
题目描述
众所周知二分查找的 在计算时可以取 或者 ,于是有选择困难症的 同学在自己的二分查找代码中加入了随机化,每次随机选取其中的一个作为 。
注意,选取不同的 mid 其他参数也会受到影响,请以代码为准。
现在 给你了二分查找使用的序列(保证为单调递增)以及他想要寻找的数(保证在序列内),他想知道在运气最好的情况下循环需要进行几次(即代码中 的可能的最终值的最小值)。
循环:
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);
}
注:以上两代码完全等价。
在此对上述代码中的 的作用做进一步阐释。
例如对于区间 ,有 个成员。虽然 的取值会因为 的取值改变而改变,但是最终确定的区间一定是 或 ,选手可以就上述代码自行模拟。
对于区间 ,有 个成员。 的取值与 的取值无关,但是 和 的取值会受到 的影响,最终确定的区间可能是 ,()或 ,()。
输入格式
第一行给出一个整数 表示序列长度。
第二行给出单调递增的 个整数表示 的序列。
第三行一个整数 表示询问的次数。
接下来 行每行一个整数表示需要查询的数字。
输出格式
对于每个询问回答一个整数,表示最小的循环次数。
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 解释
找 :
取 。
取 。
取 (退出循环)。
样例 2 解释
查询 的位置。
$$[1,13] \stackrel{w=0}{\longrightarrow} [1,7]\stackrel{w=0}{\longrightarrow}[5,7] \stackrel{w=1}{\longrightarrow} [5,5] $$数据范围及约定
本题采用捆绑测试,共有 个 ,最终分数为所有 分数之和。
$$\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} $$对于 的数据,保证 ,,。
本题有 extra sub。