GDUT-寒假专题训练1--二分查找

题目:

给定一个严格单调的数列,询问若干个数分别需要在数列中二分几次才能找到。如果能找到,输出二分的次数;如果不能找到,输出 NONE。二分查找参考程序如下:

(数列单调递增时)

l = 1, r = n, cnt = 0;
while (l <= r) {
    mid = (l + r) / 2;
    cnt++;
    if (a[mid] == key) break;
    if (a[mid] > key) r = mid - 1;
    else l = mid + 1;
}

(数列单调递减时)

l = 1, r = n, cnt = 0;
while (l <= r) {
    mid = (l + r) / 2;
    cnt++;
    if (a[mid] == key) break;
    if (a[mid] > key) l = mid + 1;
    else r = mid - 1;
}

上述程序中结束时 cntcnt 的值即为二分次数。

输入格式

第一行两个整数 n,mn,m 分别表示数列长度和询问次数。

第二行 nn 个整数,第 ii 个表示 a_iai​。

接下来 mm 行,每行一个整数 xx 表示要求询问的数。

输出格式

共 mm 行,如果能找到,输出二分的次数;如果不能找到,输出 NONE

数据范围

对于 40\%40% 的数据:1 \leq n\leq 10^6,1\leq m\leq 10^6,1\leq x,a_i\leq 10^61≤n≤106,1≤m≤106,1≤x,ai​≤106。

对于 100\%100% 的数据:1\leq n\leq 10^6,1\leq m\leq 5\times 10^6,1\leq x,a_i\leq 10^61≤n≤106,1≤m≤5×106,1≤x,ai​≤106。

提示:

读入/出数据量较大,请使用 scanf/printf

在函数声明或定义中,函数返回类型前加上关键字 inline,即可以把函数指定为内联函数。这样可以解决一些频繁调用的函数大量消耗栈空间(栈内存)的问题,也能在一定程度上减少函数反复调用时消耗的时间。

样例1输入:

10 4
1 2 3 5 7 9 11 12 13 14
7
6
5
4

样例1输出:

1
NONE
4
NONE

(对于样例 11,77 的二分过程为 [1,10],a_5=7[1,10],a5​=7。二分次数为 11;不存在 a_i=6ai​=6;55 的二分过程为 [1,10],[1,4],[3,4],[4,4],a_5=5[1,10],[1,4],[3,4],[4,4],a5​=5。二分次数为 44;不存在 a_i=4ai​=4。)

样例2输入:

8 4
20 18 15 10 9 8 5 4
1
2
10
40

样例2输出:

NONE
NONE
1
NONE

(对于样例 22,不存在 a_i=1ai​=1;不存在 a_i=2ai​=2 ;1010 的二分过程为 [1,8],a_4=10[1,8],a4​=10;不存在 a_i=40ai​=40。)

题解:该题是二分查找的模板题,但是数据较大,读入要用快读,输出最好用printf。同时注意到,询问的数组的固定的,所以可以对数组进行提前处理并储存就不会超时啦~

代码:

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iomanip>
#include<fstream>
using namespace std;
int bb[1000006]={},a[1000006],n,m,e,d,c,l,r,b;

inline int read()//快读
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}

inline void OKK(int l,int r,int h)//h是二分寻找的次数
{
	if (r<l) return;
	bb[a[(l+r)/2]]=h;//存储查询次数
	OKK(l,(l+r)/2-1,h+1);//左段
	OKK((l+r)/2+1,r,h+1);//右端
}

int main()
{
	freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	  a[i]=read();
	OKK(1,n,1);  //预处理
	for (int i=1;i<=m;i++)
	{
		b=read();
		if (bb[b]!=0) printf("%d\n",bb[b]);
		else printf("%s\n","NONE"); 
	}
    fclose(stdin);
    fclose(stdout);
}

上一篇:Microsoft Windows TCP/IP拒绝服务漏洞


下一篇:2020/2/22-2