AOJ 0033 Ball

题意

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

代码

一开始我先测试了一下自己理解的题意是不是对的：

#include <iostream>
#include <vector>  

using namespace std;

int main() {
    vector<int> left;
    vector<int> right;
    vector<int> all;

    bool flag = true;

    int n;
    cin >> n;
    if (n == 0) return -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            int temp;
            cin >> temp;
            all.push_back(temp);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            if (left.size() > 0) {
                if (all[10 * i + j] > left[left.size() - 1]) {
                    left.push_back(all[10 * i + j]);
                }
                else {
                    if (right.size() > 0) {
                        if (all[10 * i + j] > right[right.size() - 1])
                            right.push_back(all[10 * i + j]);
                        else
                            flag = false;
                    }
                    else {
                        right.push_back(all[10 * i + j]);
                    }
                }
            }
            else {
                left.push_back(all[10 * i + j]);
            }
        }

        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        flag = true;
    }

    return 0;
}

后来提交代码居然错了，什么鬼！！我用题目中的用例测试是对的啊，还是没有发现原因在哪……

因为知道题意是要求用DFS，所以改改代码，思路一样，再试试：

#include<stdio.h>
#include <queue>
using namespace std;

bool flag = true;

void solve(queue<int> left, queue<int> right, queue<int> all) {
    if (all.size() > 0) {
        if (left.size() > 0) {
            if (all.front() > left.back()) {
                left.push(all.front());
                all.pop();
                solve(left, right, all);
            }
            else {
                if (right.size() > 0) {
                    if (all.front() > right.back()) {
                        right.push(all.front());
                        all.pop();
                        solve(left, right, all);
                    }
                    else if(all.size() == 0){

                    }
                    else {
                        flag = false;
                    }
                }
                else {
                    right.push(all.front());
                    all.pop();
                    solve(left, right, all);
                }
            }
        }
        else {
            left.push(all.front());
            all.pop();
            solve(left, right, all);
        }
    }
}

int main() { 
    int n;
    scanf("%d", &n);
    for (; n > 0; n--) {
        queue<int> all;
        queue<int> left;
        queue<int> right;
        for (int i = 0; i < 10; i++) {
            int temp;
            scanf("%d", &temp);
            all.push(temp);
        }
        solve(left, right, all);
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }   
    return 0;
}

这次终于可以了，证明我的思路没有问题的呀！

找了份代码过来，变量挺多的：

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

int main() {
    stack<int> b, c;
    int a[10];
    bool which[11];
    int data[11];
    int index;
    int n, m, A;
    int i, j;
    cin >> n;
    for (i = 0; i<n; i++) {
        index = 0;
        for (j = 0; j<10; j++) {
            cin >> m;
            a[j] = m;
            data[j + 1] = 0;
        }
        b.push(0);
        c.push(0);
        while (index >= 0) {
            A = a[index];
            if (b.top() < A && (data[A] != 1 && data[A] != 3)) {
                b.push(A);
                data[A] += 1;
                which[A] = true;
            }
            else if (c.top() < A && (data[A] != 2 && data[A] != 3)) {
                c.push(A);
                data[A] += 2;
                which[A] = false;
            }
            else {
                index--;
                if (index < 0) {
                    break;
                }
                else if (which[a[index]]) {
                    b.pop();
                }
                else {
                    c.pop();
                }
                continue;
            }
            index++;
            if (index > 9) {
                cout << "YES" << endl;
                break;
            }
        }
        if (index < 0) {
            cout << "NO" << endl;
        }
    }
}