二分查找 BestCoder Round #36 ($) Gunner-白红宇

二分查找 BestCoder Round #36 ($) Gunner

阅读量：6690 次

发布时间：2019-06-25

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

1 /* 2     题意：问值为x的个数有几个，第二次查询就是0 3     lower/upper_bound ()函数的使用，map也可过，hash方法不会 4 */ 5 #include 
     
       6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 #include 
          
           11 #include 
           
            12 #include 
            13 #include 
             
              14 using namespace std;15 16 const int MAXN = 1e6 + 10;17 const int INF = 0x3f3f3f3f;18 int a[MAXN], b[MAXN];19 int used[MAXN];20 int n, m;21 22 inline int read(void)23 {24 int x = 0, f = 1; char ch = getchar ();25 while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar ();}26 while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar ();}27 return f * x;28 }29 30 int main(void) //HDOJ 5199 Gunner31 {32 //freopen ("B.in", "r", stdin);33 34 while (scanf ("%d%d", &n, &m) == 2)35 {36 memset (used, 0, sizeof (used));37 for (int i=1; i<=n; ++i) a[i] = read ();38 for (int i=1; i<=m; ++i) b[i] = read ();39 40 sort (a+1, a+1+n);41 for (int i=1; i<=m; ++i)42 {43 int x = upper_bound (a+1, a+1+n, b[i]) - a;44 int y = lower_bound (a+1, a+1+n, b[i]) - a;45 if (used[x])46 {47 puts ("0"); continue;48 }49 used[x] = 1;50 printf ("%d\n", x - y);51 }52 }53 54 return 0;55 }

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
          5 using namespace std; 6  7 const int MAXN = 1e6 + 10; 8 const int INF = 0x3f3f3f3f; 9 10 inline int read(void)11 {12     int x = 0, f = 1;    char ch = getchar ();13     while (ch < '0' || ch > '9')    {
      if (ch == '-') f = -1;    ch = getchar ();}14     while (ch >= '0' && ch <= '9')    {x = x * 10 + ch - '0';    ch = getchar ();}15     return f * x;16 }17 int main(void)18 {19     //freopen ("B.in", "r", stdin);20 21     int n, m;22     while (scanf ("%d%d", &n, &m) == 2)23     {24         map
          
            ma;    int x;25         while (n--)26         {27             x = read ();   ma[x]++;28         }29         map
           
            ::iterator it;30 while (m--)31 {32 x = read ();33 it = ma.find (x);34 if (it == ma.end ())35 puts ("0");36 else37 {38 printf ("%d\n", it->second);39 it->second = 0;40 }41 }42 }43 44 return 0;45 }