nyoj--86--找球号(一）(hash&&set&&二分)

找球号(一）

时间限制：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 4

23 34 46 768 343 343

2 4 23 343

样例输出

NO

NO

YES

YES

set

常用操作：

1.元素插入：insert()

2.中序遍历：类似vector遍历（用迭代器）

3.反向遍历：利用反向迭代器reverse_iterator。

   例：

   set<int> s;

   ......

   set<int>::reverse_iterator rit;

   for(rit=s.rbegin();rit!=s.rend();rit++)

4.元素删除：与插入一样，可以高效的删除，并自动调整使红黑树平衡。

           set<int> s;

           s.erase(2);       //删除键值为2的元素

           s.clear();

5.元素检索：find()，若找到，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置。

           set<int> s;

           set<int>::iterator it;

           it=s.find(5);   //查找键值为5的元素

           if(it!=s.end())   //找到

               cout<<*it<<endl;

           else           //未找到

               cout<<"未找到";

6.自定义比较函数

   (1)元素不是结构体：

       例：

       //自定义比较函数myComp,重载“（）”操作符

       struct myComp

       {

           bool operator()(const your_type &a,const your_type &b)

           [

               return a.data-b.data>0;

           }

       }

       set<int,myComp>s;

       ......

       set<int,myComp>::iterator it;

   (2)如果元素是结构体，可以直接将比较函数写在结构体内。

       例：

       struct Info

       {

           string name;

           float score;

           //重载“<”操作符，自定义排序规则

           bool operator < (const Info &a) const

           {

               //按score从大到小排列

               return a.score<score;

           }

       }

       set<Info> s;

       ......

       set<Info>::iterator it;

//转载

#include<stdio.h>

#include<set>

#include<algorithm>

using namespace std;

int main()

{

	int m,n,a;

	set<int>s;

	scanf("%d%d",&m,&n);

	while(m--)

	{

		scanf("%d",&a);

		s.insert(a);

	}

	while(n--)

	{

		scanf("%d",&a);

		if(s.find(a)!=s.end())

		printf("YES\n");

		else

		printf("NO\n");

	}

	return 0;

}

hash

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int a[10001000];

int main()

{

	int m,n,x;

	scanf("%d%d",&m,&n);

	while(m--)

	{

		scanf("%d",&x);

		a[x/32]=1<<x%32;

	}

	while(n--)

	{

		scanf("%d",&x);

		if(a[x/32]&(1<<x%32))

		printf("YES\n");

		else

		printf("NO\n");

	}

	return 0;

}

二分查找

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int a[1000100];

int main()

{

	int m,n;

	scanf("%d%d",&m,&n);

	for(int i=0;i<m;i++)

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

	sort(a,a+m);

	while(n--)

	{

		int mid,k;

		scanf("%d",&k);

		int flog=0;

		int l=0,r=m;

		while(l<=r)

		{

			mid=(l+r)/2;

			if(a[mid]==k)

			{

				flog=1;

				break;

			}

			else if(k<a[mid])

			r=mid-1;

			else

			l=mid+1;

		}

		if(flog)

		printf("YES\n");

		else

		printf("NO\n");

	}

	return 0;

}

巴特西

nyoj--86--找球号(一）(hash&&set&&二分)

找球号(一）

最新文章

热门文章