土拨鼠掷鼬鼠

爱被打了一巴掌 2022-12-28 15:27 159阅读 0赞

## 土拨鼠掷鼬鼠 ##

Description  
神奇的土拨鼠今天又很乖的皮的玩起了鼬鼠，今天依旧是掷鼬鼠。土拨鼠忘记了自己家周围有着 nn 圈的着火带。已知距离土拨鼠 r\[i\]r\[i\] (1 \\leqslant i \\leqslant n)(1⩽i⩽n) 的位置处有一圈着火地带。现在土拨鼠有 mm 次投掷，告诉你它投掷的距离 L\[i\]L\[i\] (1 \\leqslant i \\leqslant m)(1⩽i⩽m)，问你当前投掷的鼬鼠会不会解脱 gg 掉，也就是落在着火地带上（当前仅当 L\[i\]L\[i\] == r\[j\]r\[j\] (1 \\leqslant j \\leqslant n)(1⩽j⩽n) 时，我们认为鼬鼠落在了着火带上）。

Input  
第一行是以空格分隔的两个整数 nn, mm。nn 表示着火带的圈数，mm 表示投掷的次数。

接下来一行 nn 个整数 r\[i\]r\[i\]，表示距离土拨鼠家 r\[i\]r\[i\] 的位置处有一圈着火带。

接下来 mm 行，每行一个整数 L\[i\]L\[i\]，表示土拨鼠投掷的距离。

(1 \\leqslant n, m \\leqslant 10^\{5\})(1⩽n,m⩽10  
5  
)  
(1 \\leqslant r\[i\], L\[i\] \\leqslant 10^\{9\})(1⩽r\[i\],L\[i\]⩽10  
9  
)  
Output  
输出有 mm 行，每行对于每次询问，如果鼬鼠会落在着火带上输出 GG!，否则输出 The world is so beautiful~。

Sample  
Input  
5 5  
1 4 5 7 8  
10  
4  
3  
6  
5  
Output  
The world is so beautiful~  
GG!  
The world is so beautiful~  
The world is so beautiful~  
GG!

#include <bits/stdc++.h>
    using namespace std;
    int a[1000010];
    int Half(int l, int r, int key)//二分查找
    {
        
    	int mid;
    	if (l <= r)
    	{
        
    		mid = (l + r) / 2;
    		if (a[mid] == key)
    			return 1;
    		else if (a[mid] > key)
    			return Half(l, mid - 1, key);
    		else
    			return Half(mid + 1, r, key);
    	}
    	return 0;
    }
    int main()
    {
        
    	int m, n;
    	scanf("%d %d", &n, &m);
    	for (int i = 0; i < n; i++)
    	{
        
    		scanf("%d", &a[i]);
    	}
    	sort(a, a + n);//快速排序
    	for (int i = 0; i < m; i++)
    	{
        
    		int key, flag;
    		scanf("%d", &key);
    		flag = Half(0, n-1, key);
    		if (flag)
    			printf("GG!");
    		else
    			printf("The world is so beautiful~");
    		if (i != m - 1)
    			printf("\n");
    	}
    }