数组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.

评论

暂无评论