1.4.1 好多好多道符（题解）

1.4.1 好多好多道符

Description

云之界是一个拥有着道法的世界，这个世界拥有着各种各样的魔法。

曾经有位大贤，将各种仙法编纂进了《道法三千》的书中，并给每种道法一个编号。书名虽然唤作《道法三千》，但是实际上的道法数远远超过三千，这本书现在已经是云之界广泛流行，于是，各大门派都使用这本书中的道法编号来标识道法。

小云是修行世家，然而天赋奇差，难以修习道法。所幸小云拥有大量家族赐予的道符，使用道符可以直接使用道法。

每张道符上有一个道法编号，代表这张道符可以直接使用出来的道法。

小云心中有qqq个诸如“ bib_ibi​ 道法我能否使用”的问题。由于小云的道符和疑问太多了，所以，它需要神奇的你来帮助他。

Input

第一行一个整数 n n n 。表示道符张数。

第二行 n n n 个以空格隔开的整数，第i个数表示 ai a_i ai​ 。含义见题目描述。

第三行一个正整数 q q q . 表示小云的疑问数。

第四行 q q q 个以空格隔开的正整数，第i个数表示  bi b_i bi​  。含义见题目描述。

Output

输出仅一行，为一个长度为nnn的字符串s。当小云可以使用出道法bib_ibi​时输出si=s_i=si​='Y',否则 si=s_i=si​= ‘N’.

Sample Input 1

10
5 5 6 8 8 9 12 23 41 79
15
50 8 9 23 233 5 6 8 79 12 5 8 9 41 22

Sample Output 1

NYYYNYYYYYYYYYN

Hint

数据范围：

50%的数据有：1≤n,q≤50001 \le n,q \le 50001≤n,q≤5000

100%的数据有：1≤n,q≤1061 \leq n,q \le 10^61≤n,q≤106

1≤ai,bi≤q≤231−11 \leq a_i, b_i\le q \le 2^{31}-11≤ai​,bi​≤q≤231−1

  

   

    

     

    
    

     

      #include <bits/stdc++.h>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      int a[1001000];
     
    
   

    

     

    
    

     

      int n,q,b;
     
    
   

    

     

    
    

     

      string S;
     
    
   

    

     

    
    

     

      //直接二分
     
    
   

    

     

    
    

     

      int find(int x)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int l=1,r=n;
     
    
   

    

     

    
    

     
    while(l<=r){
     
    
   

    

     

    
    

     
        int mid=(l+r)>>1;
     
    
   

    

     

    
    

     
        if(x==a[mid])return 1;
     
    
   

    

     

    
    

     
        else if(x<a[mid])r=mid-1;
     
    
   

    

     

    
    

     
        else l=mid+1;
     
    
   

    

     

    
    

     

          }//objective1 如何二分？(真的再给提示就直接是代码了QWQ --Megumin)
     
    
   

    

     

    
    

     
    return -1;// Not found
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    scanf("%d",&n);
     
    
   

    

     

    
    

     
    for(int i = 1;i <= n;i ++)
     
    
   

    

     

    
    

     
        scanf("%d",&a[i]);
     
    
   

    

     

    
    

     
    scanf("%d",&q);
     
    
   

    

     

    
    

     
    for(int i = 1;i <= q;i ++){
     
    
   

    

     

    
    

     
        scanf("%d",&b);
     
    
   

    

     

    
    

     
        if(find(b) != -1)
     
    
   

    

     

    
    

     

                  S += 'Y';
     
    
   

    

     

    
    

     
        else
     
    
   

    

     

    
    

     

                  S += 'N';
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          cout<<S;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

  

   

    

     

    
    

     
 while(l<=r){
     
    
   

    

     

    
    

     
        int mid=(l+r)>>1;
     
    
  
 

看了CSDN的其他文章，发现二分真是个好东西，但是注意两个地方：<= 和>>1

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120579472