nyoj 86 找球号(一）(set,map)-白红宇

nyoj 86 找球号(一）(set,map)

阅读量：5110 次

发布时间：2019-06-13

本文共 2108 字，大约阅读时间需要 7 分钟。

找球号(一）

时间限制：3000 ms | 内存限制：65535 KB

难度：3

描述

在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，现在说一个随机整数k(0<=k<=100000100)，判断编号为k的球是否在这堆球中（存在为"YES",否则为"NO"），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。

输入

第一行有两个整数m，n(0<=n<=100000，0<=m<=1000000)；m表示这堆球里有m个球，n表示这个游戏进行n次。接下来输入m+n个整数，前m个分别表示这m个球的编号i，后n个分别表示每次游戏中的随机整数k

输出

输出"YES"或"NO"

样例输入

6 423 34 46 768 343 3432 4 23 343

样例输出

NONOYESYES 首先数据很多，用scanf和printf 解法一：用set集合

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 using namespace std; 6  7 int main(){ 8     int m, n, i, k; 9     set
           
             s;10     scanf("%d %d", &m, &n);11     while(m--) {12         scanf("%d", &i);13         s.insert(i);14     }15 16     while(n--){17         scanf("%d", &k);18         if(s.find(k) != s.end())19             printf("YES\n");20         else21             printf("NO\n");22     }23     return 0;24 }

二分查找也可以，但是数据太多，而且输入的数据是无序的，用二分查找还得先排序，

1   2 #include
       
         3 #include
        
          4 #include
         
           5 #define M 1000010 6  7 using namespace std; 8  9 int a[M];10 11 bool find(int key,int s,int e)12 {13     int m;14     while(s<=e)15     {16         if(key
          
           a[e]) return false;17         m=(s+e)/2;18         if(key==a[m]) return true;19         else if(key

用map，

1 #pragma warning(disable:4786) 2 #include 
       
         3 #include 
        
          4 #include 
          5 #include 
          
            6 #include 
           
             7 using namespace std; 8  9 int main(){10     int i;11     map
            
              mp;12 int m, n;13 scanf("%d%d", &m, &n);14 for(i = 0; i < m; i++){15 int temp;16 scanf("%d", &temp);17 if(!mp.count(temp))18 mp[temp] = 0;19 mp[temp]++;20 }21 for(i = 0; i < n; i++){22 int temp;23 scanf("%d", &temp);24 if(mp.count(temp))//mp.find(temp) != mp.end()25 printf("YES\n");26 else27 printf("NO\n");28 }29 return 0;30 }

转载于:https://www.cnblogs.com/qinduanyinghua/p/5718424.html

你可能感兴趣的文章