学步园

找球号(一）

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

 

#include

#include

#include

using namespace std;

int a[1000000];

int b[100000];

int main()

{

int m,n,i;

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

for(i=0;i

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

sort(a,a+m);

for(i=0;i

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

for(i=0;i

{

int low = 0,high = m-1,mid;

int flag=0;

while(low <= high)

{

mid =(low+high)/2;

if(b[i]==a[mid]){  flag=1;break; }

else if( b[i]

else low = mid + 1;

}

if(flag) cout<<"YES\n";

else cout<<"NO\n";

}

return 0;

}      
 

 

#define LH +1

#define EH 0

#define RH -1

#define ElemType int

#define Status int

#define FALSE 0

#define TRUE 1

typedef struct BSTNode

{

ElemType data;

int bf; // 节点的平衡因子

struct BSTNode * lchild, * rchild; //左右孩子指针

}BSTNode, * BSTree;

#include

#include

#include

using namespace std;

void R_Rotate(BSTree & p)

{

//对以*p 为根的二叉排序树做右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点

BSTree lc;

lc = p->lchild;//lc指向p的左子树

p->lchild = lc->rchild;//p左子树lc的有右子树

lc->rchild = p; //lc右子树指向p

p = lc;//p指向新的根结点

}//R_Rotate

void L_Rotate(BSTree & p)

{

//对以*p 为根的二叉排序树做左旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点

BSTree rc;

rc = p->rchild;//rc指向p的左子树

p->rchild = rc->lchild;//p左子树rc的左子树

rc->lchild = p; //rc左子树指向p

p = rc;//p指向新的根结点

}//R_Rotate

void LeftBalance( BSTree & T)

{

BSTree lc,rd;

lc = T->lchild;

switch(lc->bf)

{

case LH:

lc->bf = T->bf = EH;

R_Rotate(T); break;

case RH:

rd = lc->rchild;

T->lchild = rd->rchild;

lc->rchild = rd->lchild;

rd->lchild = lc;

rd->rchild = T;

T = rd;

}//switch(lc->bf)

}//LeftBalance

void RightBalance( BSTree & T)

{

BSTree rc,rd;

rc = T->rchild;

switch(rc->bf)

{

case RH:

rc->bf = T->bf = EH;

L_Rotate(T); break;

case LH:

rd = rc->lchild;

T->rchild = rd->lchild;

rc->lchild = rd->rchild;

rd->rchild = rc;

rd->lchild = T;

T = rd;

}//switch(rc->bf)

}//RightBalance

Status InsertAVL ( BSTree &T , ElemType e, bool
&taller )

{//若平衡二叉树中不存在e，则插入新节点e返回1，否则返回0.
 若因插入结点使树不平衡，进行旋转，taller代表树是否长高

if(!T){ //空树，直接插入

T = (BSTNode *)malloc(sizeof(BSTNode)); T->data =
e; 

T->lchild = T->rchild = NULL; T->bf = EH; taller =
true;

}

else {

if(e == T->data) {   taller= false; return
0;}  //已存在e

if(e < T->data)  { //
e<根结点，向左查找左子树

if(!InsertAVL(T->lchild,e,taller) )  
 return 0;///未插入

if( taller )  //已插入左子树并使树长高

switch (T->bf)//检察 T 的平衡度

{

case LH: //原左子树高于右子树，则左平衡处理

LeftBalance(T); taller = false; break;

case EH:

T->bf = LH; taller = true; break;

case RH:

T->bf = EH; taller = false; break;

}

}//if

else

{

if(!InsertAVL(T->rchild,e,taller) )  
 return 0;

if( taller )

switch (T->bf)

{

case LH:

T->bf = EH;taller = false; break;

case EH:

T->bf = RH; taller = true; break;

case RH:

RightBalance(T); taller = false; break;

}

}//else

}//else

return 1;

}//InsertAVL

Status SearchBST (BSTree T, ElemType key)

{

if (!T)    return FALSE;
  // 查找不成功

else  if ( key == T->data)
 return TRUE;   // 查找成功

else  if ( key < T->data )
 SearchBST (T->lchild, key);  
 // 在左子树中继续查找

else  SearchBST (T->rchild, key);
     
     //
在右子树中继续查找

} // SearchBST

int b[100000];

int main()

{

BSTree T,p;

T = NULL;

bool taller;

int m,n,e;

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

while(m--)

{

scanf("%d",&e);

InsertAVL(T,e,taller);

}

for(int i=0;i

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

for(int i=0;i

{

if( SearchBST(T,b[i]) ) printf("YES\n");

else printf("NO\n");

}

return 0;

}