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

题目传送门

 /*
题意:问值为x的个数有几个,第二次查询就是0
lower/upper_bound ()函数的使用,map也可过,hash方法不会
*/
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std; const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
int a[MAXN], b[MAXN];
int used[MAXN];
int n, m; inline int read(void)
{
int x = , f = ; char ch = getchar ();
while (ch < '' || ch > '') {if (ch == '-') f = -; ch = getchar ();}
while (ch >= '' && ch <= '') {x = x * + ch - ''; ch = getchar ();}
return f * x;
} int main(void) //HDOJ 5199 Gunner
{
//freopen ("B.in", "r", stdin); while (scanf ("%d%d", &n, &m) == )
{
memset (used, , sizeof (used));
for (int i=; i<=n; ++i) a[i] = read ();
for (int i=; i<=m; ++i) b[i] = read (); sort (a+, a++n);
for (int i=; i<=m; ++i)
{
int x = upper_bound (a+, a++n, b[i]) - a;
int y = lower_bound (a+, a++n, b[i]) - a;
if (used[x])
{
puts (""); continue;
}
used[x] = ;
printf ("%d\n", x - y);
}
} return ;
}
 #include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
using namespace std; const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f; inline int read(void)
{
int x = , f = ; char ch = getchar ();
while (ch < '' || ch > '') {if (ch == '-') f = -; ch = getchar ();}
while (ch >= '' && ch <= '') {x = x * + ch - ''; ch = getchar ();}
return f * x;
}
int main(void)
{
//freopen ("B.in", "r", stdin); int n, m;
while (scanf ("%d%d", &n, &m) == )
{
map<int, int> ma; int x;
while (n--)
{
x = read (); ma[x]++;
}
map<int, int>::iterator it;
while (m--)
{
x = read ();
it = ma.find (x);
if (it == ma.end ())
puts ("");
else
{
printf ("%d\n", it->second);
it->second = ;
}
}
} return ;
}

map

上一篇:BestCoder Round #36 (hdu5198)Strange Class(水题)


下一篇:BestCoder Round #36 (hdu5200)Strange Class(离线)