(eden)Shooting Game

Description:

Erin最近很喜欢玩射击游戏。她刚考完了C语言的期末考试，感觉很溜，于是又来到了射击娱乐场放松一下。和上次一样，先从老板那租了一把步枪和装有N发子弹的弹夹。在射击的过程中，Erin每次都有两种选择：从弹夹中取出一颗子弹上膛，或者打一发子弹出去。注意：所有的子弹都从枪口上膛。Erin感觉这有点像C语言课程中的“栈”的特点。因此在打完了这N发子弹之后，她想验证一下这些子弹打出来的顺序是不是真的满足“栈”的特性。假设N颗子弹的编号为1,2,…,N。子弹从弹夹中取出的顺序也是从1到N。给定一个子弹被打出的顺序，你可以帮Erin验证其是否满足“栈”的打出顺序吗？

可能有多个测试输入，第一行给出总共的测试输入的个数T，和每个测试输入的子弹数N。(0 < T < 20, 0 < N < 10)

每个测试输入只有一行：用空格隔开的N个数，表示子弹打出的编号顺序。

输出YES或者NO表示判断结果

例如

INPUT：

2 4

4 3 2 1

4 2 3 1

OUTPUT:

YES

NO

 

Hint:

用数组就能解决了，大家想清楚判断逻辑再动手。

万一坑了请评论区提醒，谢谢。

代码

#include<stdio.h>
int main() {
    int t, n, i, j;
    scanf("%d%d", &t, &n);
    for (i = 1; i <= t; i++) {
        int k;
        int b[15] = {0};
        scanf("%d", &k);
        b[k] = 1;
        for (j = n; j > 1; j--) {
            int move;
            scanf("%d", &move);
            if (move > k) {
                k = move;
                b[k] = 1;
                continue;
            } else {
                int pd = k;
                while (b[pd] != 0) pd--;
                if (pd == move) {
                    k = move;
                    b[k] = 1;
                    continue;
                } else {
                    printf("No
");
                    int jj, xiaochu;
                    for (jj = j - 1; jj > 1; jj--) {
                        scanf("%d", &xiaochu);
                    }
                    break;
                }
            }
        }
        if (j == 1) printf("Yes
");
    }
}

解释

以栈的方式走一个就是打出前面放入的一个子弹（没有打出来过的）不能够是前面第二个，要紧贴着当前这一个，要么就是打出后面的子弹（还没有放入），但是后面任意一个都可以，因为可以一直一个一个放子弹，然后如果这两种情况有一个满足，说明下面那个点是可以走的，就把该点设为当前考虑点，循环上面的步骤；

                 {要么走前面一个没有走过的点}

第一个点进入{要么走后面任意一个可以走的点}再把当前的点设置为现在考虑的点；

标程

1.#include<stdio.h>
2.int main() {
3.    int t, n;
4.    scanf("%d %d", &t, &n);
5.    while (t--) {
6.        int s[15] = {};
7.        int temp;  // 存放s[i]之后可能存在的第一个比s[i]小的
8.        int flag1;  // 标识s[i]之后是否存在比s[i]小的
9.        int flag2;  // 标识出栈序列是否非法
10.        int i, j, k;
11.        for (i = 1; i <= n; i++)
12.            scanf("%d", &s[i]);
13.        for (i = 1; i < n; i++) {
14.            flag1 = 0;
15.            flag2 = 0;
16.            for (j = i + 1; j <= n; j++)  // 寻找s[i]之后第一个比s[i]小的
17.                if (s[j] < s[i]) {  // s[i]之后存在比s[i]小的
18.                    temp = s[j];  // s[j]是s[i]之后第一个比s[i]小的
19.                    flag1 = 1;
20.                    break;
21.                }
22.            if (flag1 == 1)
23.                for (k = j + 1; k <= n; k++)
24.                    if (s[k] < s[i])  // s[j]之后如果还有比s[i]小的数
25.                        if (s[k] >= temp) {  // 出栈序列非法
26.                            flag2 = 1;
27.                            break;
28.                        }
29.                        else  // 都必须小于它之前的一个比s[i]小的数
30.                            temp = s[k];  // 更新temp
31.            if (flag2 == 1) {
32.                printf("No
");
33.                break;
34.            }
35.        }
36.        if (flag2 == 0)
37.            printf("Yes
");
38.        }
39.        return 0;
40.}