AOJ 0033 Ball -电脑资料

电脑资料 时间:2019-01-01 我要投稿
【www.unjs.com - 电脑资料】

   

题意

   

    题目我截图下来了,我大致解释下,

AOJ 0033 Ball

。有编号1到10共10个球,从上方丢下去,入口处可以选择进入左边或者右边,最后10个球全部落下去后如果左右两侧都是从小到大的顺序,则输出YES;否则输出NO。<喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxpbWcgYWx0PQ=="这里写图片描述" src="http://www.2cto.com/uploadfile/Collfiles/20151213/20151213091427178.jpg" title="\" />

代码

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

<code class="hljs cpp">#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;}</int></int></int></vector></iostream></code>

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

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

<code class="hljs cpp">#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;}</int></int></int></int></int></int></queue></stdio.h></code>

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

    找了份代码过来,变量挺多的:

<code class="hljs cpp">#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; cin="" for="" index="0;" j="0;">> 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;        }    }}</n;></int></queue></stack></iostream></code>

最新文章