UPC——问题 O: 美人松高度2

题目描述

又到过年了，狗熊岭的动物们都忙碌起来，张灯结彩准备过年。李老板却要光头强砍掉一些百年美人松回去。美人松都是很高的，但是也不会超过长整型（long long)。现在光头强看到丛林里有N颗美人松按照从矮到高排好了，当然每棵松的高度都是已知的。李老板要问光头强M次：每次询问高度为K的美人松是否存在？

输入

第一行，两个正整数N，M,1<=N<=10^6,1<=M<=10^3;
第二行，N个正整数，之间用一个空格隔开，表示N棵美人松的高度；
第三行M个正整数k，表示M个询问，每次询问高度为K的美人松是否存在，1<=k<=1000。
（提示：要用scanf读入，否则会超时）

输出

一行M个正整数，之间用一个空格隔开，分别表示对应每次询问高度为K的树的查询结果，如果存在，则输出1，不存在则输出0

样例输入 Copy

5 2
2 3 3 4 5
3 6

样例输出 Copy

1 0

解题思路：本题是对某一指定元素进行查找， 很容易想到用二分。

Code:

#include 
#include 
#include using namespace std;typedef long long LL;const int N = 100010;int a[N], b[N];
int n, m, f, s, x;signed main()
{cin >> n >> m;for(int i = 0; i <= n - 1; i ++ )  scanf("%d", &a[i]);sort(a, a + n);for(int i = 1; i <= m; i ++ ){cin >> x;int l = 0, r = n - 1;while(l < r){int mid = l + r >> 1;if(a[mid] >= x)  r = mid;else  l = mid + 1;}if(a[l] != x)  cout << 0 << ' ';else  cout << 1 << ' ';}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！