数组I 问题O : 美人松高度2
文章目录
题目描述
又到过年了,狗熊岭的动物们都忙碌起来,张灯结彩准备过年。李老板却要光头强砍掉一些百年美人松回去。美人松都是很高的,但是也不会超过长整型(long long)。现在光头强看到丛林里有N颗美人松按照从矮到高排好了,当然每棵松的高度都是已知的。李老板要问光头强M次:每次询问高度为K的美人松是否存在?
输入
第一行,两个正整数N,M,1<=N<=10^6,1<=M<=10^3;
第二行,N个正整数,之间用一个空格隔开,表示N棵美人松的高度;
第三行M个正整数k,表示M个询问,每次询问高度为K的美人松是否存在。
(提示:要用scanf读入,否则会超时)
输出
一行M个正整数,之间用一个空格隔开,分别表示对应每次询问高度为K的树的查询结果,如果存在,则输出1,不存在则输出0
样例输入 Copy
5 2
2 3 3 4 5
3 6
样例输出 Copy
1 0
二分查找,代码详细解释在下面。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
long long int m,n,i,j,a,b,c,p,q;
cin>>n>>m;
long long int h[n];
for(i=0;i<n;i++)
{
scanf("%lld" ,&h[i]);//输入每棵树的高度
}
sort(h,h+n);//n棵树排序
for(j=1;j<=m;j++)//m次询问
{
cin >> a;//询问的高度
long long int l=0,r=n-1;//0到n-1是n个数
while(l<r)//二分查找,找中间的那个数跟询问的a比较大小
{
b=l+r>>1;//除2取整
if(h[b]>=a)//中间值大于a往左找
{
r = b;
}
else //中间值小于a往右找
{
l = b+1;
}
}//结束循环的条件就是l=r此时
if(h[l]!=a)//不存在这个a高度的树
{
cout << 0 <<" ";
}
else //存在这个a高度的树
{
cout<<1<<" ";
}
}
}b=l+r>>1;这个就是一个除以2取整,本身含义 l+r 的值右移一位
eg:15的二进制表示是00001111,15>>1将00001111右移一位,变为00000111,即7.

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论