Aizu/Aoj 0033 Ball

　　　题目大意：有编号1到10共10个球，从上方丢下去，入口处可以选择进入左边或者右边，最后10个球全部落下去后如果左右两侧都是从小到大的顺序，则输出YES；否则输出NO。

　　题目原本的标签枚举，复杂度是2^10,,,很容易水过。我这里说的是用贪心的方法，直接扫一遍O(10)复杂度：设两个栈模拟左右两个管；对于每一个球有以下几种处理情况：

1、如果两个栈都为空，就往任意一个栈里放入小球

2、如果当前小球编号同时小于两个栈的栈顶小球编号，则直接输出"NO"

3、如果当前小球编号比其中一个栈的栈顶小球编号小，则放入另一个栈中

4、如果仅有一个栈空或都不为空，就判断当前小球编号是否为其中一个栈的栈顶小球编号数+1，是的话就放入那个栈内

5、当前小球编号都不为两个栈栈顶的小球编号数+1，那就判断哪个栈的栈顶小球编号数距其最近，就放入哪个栈

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <cstdlib>

 #include <cctype>

 #include <queue>

 #include <stack>

 #include <map>

 #include <vector>

 #include <set>

 #include <utility>

 #define ll long long

 #define inf 0x3f3f3f3f

 using namespace std;

 int a[];

 int main()

 {

     //freopen("input.txt","r",stdin);

     int n;

     scanf("%d",&n);

     while(n--)

     {

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

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

         //

         stack<int> sl,sr;

         sl.push(a[]);

         //

         bool flag=true;

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

         {

             if(!sr.empty())

             {

                 if(a[i]<sl.top()&&a[i]<sr.top())

                 {

                     flag=false;

                     break;

                 }

                 else

                 {

                     if(a[i]==sl.top()+)

                         sl.push(a[i]);

                     else if(a[i]==sr.top()+)

                         sr.push(a[i]);

                     else if(a[i]<sl.top())

                         sr.push(a[i]);

                     else if(a[i]<sr.top())

                         sl.push(a[i]);

                     else

                     {

                         if((a[i]-sl.top())<(a[i]-sr.top()))

                             sl.push(a[i]);

                         else

                             sr.push(a[i]);

                     }

                 }

             }

             else

             {

                 if(a[i]==sl.top()+)

                     sl.push(a[i]);

                 else

                     sr.push(a[i]);

             }

         }

         //

         if(flag)

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }

巴特西

Aizu/Aoj 0033 Ball

最新文章

热门文章