【Aizu - 0033】Ball （简单搜索）

-->Ball

原文是日语，这里直接写中文了

Descriptions:

如图所示，容器中间有一枢轴，下方分为两路。容器上方开口，从1到10连续编号的小球从容器开口A放入。通过调整枢轴E的方向，可以使小球经过D而落入左侧B筒或者右侧C筒。现给出从A放入小球的顺序，请你判断能否最终小球落入B和C时，号码大的球总是位于号码小的球的上侧。如果可能则在一行中输出”YES”，否则输出 “NO”

Input

第一行一个整数N(N<1000)
接下来有N行，每行10个由空格分隔的[1,10]区间内的整数，分别代表10个小球放入A筒的顺序

Output

对每组数据，输出一行YES或NOSample

Sample Input

2

3 1 4 2 5 6 7 8 9 10

10 9 8 7 6 5 4 3 2 1

Output for the Sample Input

YES

NO

题目链接：

https://vjudge.net/problem/Aizu-0033

这题被归为白书搜索题，但是我写的时候真没有用什么dfs之类的算法，就一步一步的模拟这个过程，从第二个小球搜到最后一个，可以说是模拟吧，这题不难，按照题意设置两个数组分别表示左右两个容器，然后模拟即可

AC代码：

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 25

using namespace std;

int n,m;

int a[Maxn];

int ans1[Maxn];//分别表示两边的容器

int ans2[Maxn];

int main()

{

    cin>>n;

    while(n--)

    {

        MEM(a,);//全部初始化

        MEM(ans1,);

        MEM(ans2,);

        for(int i=; i<=; i++)//读入数据

            cin>>a[i];

        ans1[]=a[];

        ans2[]=;

        int p1=,p2=;//ans1 ans2的下标

        int i;

        for(i=; i<=; i++)//一个一个往左右两个容器内放

        {

            if(a[i]>ans1[p1])

                ans1[++p1]=a[i];

            else if(a[i]>ans2[p2])

                ans2[++p2]=a[i];

            else//a[i]<ans1[p1]且a[i]<ans2[p2]

            {

                cout<<"NO"<<endl;

                break;

            }

        }

        if(i>)

            cout<<"YES"<<endl;

    }

}

巴特西

【Aizu - 0033】Ball （简单搜索）

-->Ball

最新文章

热门文章