NYOJ—题目88 找球号(一）

女爷i 2022-08-25 05:29 102阅读 0赞

找球号(一）

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

样例输出

YES

方法一：一维数组，折半查找（简单，执行速度快）

\#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

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

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;

NYOJ—题目88 找球号(一）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 NYOJ 138 找球号(二）

相关 NYOJ 528 找球号（三）

相关 NYOJ 86 找球号(一）

相关 nyoj 897 数学题目 (找规律)

相关 NYOJ-题目27 水池数目

相关 NYOJ—题目88 找球号(一）

相关 NYOJ-题目221 Tree

相关喷水装置（一）--nyoj题目6

相关 Flash AS3 学习8 - 旋转的小球

相关找球号(一）