Автор: Лао Цзю — Техническое Просо.

продукт:Посмотреть исходный текст

социальный контакт:CSDN

публика:Школа Лаоцзю (для новичков есть преимущества)

Специальное заявление: Нелегко быть оригинальным, и перепечатка или плагиат не допускаются без разрешения.Если вам нужно перепечатать, вы можете связаться с автором для получения разрешения.

описание проблемы

Структура железнодорожного сообщения поездоотправочной станции представлена ​​на рисунке:

Среди них A — вход, B — выход, S — транзитный тупик. Все железные дороги однопутные и односторонние: поезда могут ехать только из А в Ю, а затем из Ю в Б, кроме того, обгон запрещен. Поскольку автомобили могут находиться в S, порядок, в котором они выезжают со стороны B, может не совпадать с порядком, в котором они въезжают со стороны A. Однако вместимость S ограничена, и количество вагонов, находящихся одновременно, не должно превышать m.

Предположим, что поезд состоит из n вагонов, пронумерованных последовательно {1, 2, …, n}. Диспетчер хочет знать, могут ли эти вагоны перестроиться в порядке {a1, a2, …, an} в соответствии с указанными выше правилами дорожного движения и покинуть сторону B. Если можно, в каком порядке это делать?

входить

Есть две линии.

Первая строка содержит два целых числа n, m.

Вторая строка представляет собой массив из n целых чисел, разделенных пробелами, гарантированно являющийся расположением {1, 2, ..., n}, представляющий выходную последовательность {a1, a2, ..., an} возможности быть судимым.

вывод

Если последовательность выезда допустима, выведите последовательность операций, в которой push указывает, что каретка входит в S из A, а pop указывает, что каретка входит в B из S, и каждая операция занимает одну строку.

Если невозможно, выведите No.

Образец

Input

Output

Код

Определить последовательную структуру стека

#include "stdio.h"
#include "stdlib.h"
#define MAX_SIZE 255    //数组最大长度
//顺序栈结构
typedef struct sqStack
{
    int elems[MAX_SIZE];
    int top; //栈顶，数组下标
    int length; //栈的长度
}SqStack;

void init(SqStack* s)
{
    s->top = -1;
    s->length = 0;
}

int push(SqStack* s, int elem)
{
    if(s->top == MAX_SIZE - 1)/*栈满*/
    {
        return 0;
    }

    s->length++;
    s->top++;   /*栈顶指针增加1*/
    s->elems[s->top] = elem;   /*将新插入元素赋值给栈顶空间*/
    return 1;
}

int pop(SqStack* s)
{
    if(s->top == 0) return 0;

    int elem = s->elems[s->top];  /*将要删除的栈顶元素赋值给e*/
    s->top--;   /*栈顶指针减1*/
    s->length--;
    return elem;
}
int main()
{
    int a[50];
    int operation[50];
    int i = 0;
    int m, n, flag = 0;
    printf("输入火车数量：");
    scanf("%d",&n); //火车数量n
    printf("输入车站最大停留数量：");
    scanf("%d",&m); //最大停留火车数量m（栈的上限）
    printf("输入出站序列：\n");
    for (i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);  //输入{1,2,...,n}
    }

    int step = 0, b = 1;

    //栈的创建并赋值
    SqStack s;
    init(&s);
    push(&s,0);

    //模拟火车进栈调度
    for (i = 0; i < n; i++)
    {
        while(s.elems[s.top] < a[i])
        {
            push(&s,b++);
            operation[step++] = 1;
        }

        //超出栈的上限（栈底放入0,上限+1）
        if (s.length > m + 1)
        {
            printf("no\n");
            flag = 1; //标识无解决方案可满足条件
            break;
        }
		//直到找到与输入的出栈顺序相等的值
        if (s.elems[s.top] == a[i])
        {
            pop(&s);
            operation[step++] = 0;
        }
    }

    if (flag != 1)
    {
        if (s.length == 1 && s.top == 0)
        {
            for (i = 0; i < step; i++)
            {
                if (operation[i] == 1)
                    printf("push\n");
                else
                    printf("pop\n");
            }
        }
        else
            printf("no\n");
    }
    return 0;
}

Суммировать

Реализация кода у нас точно не самая лучшая, если есть недочеты, прошу поправить и дополнить.

Наконец

Студенты, которые чувствуют себя полезными, не забудьте дать Дашу❤️Подписаться + Нравится + Избранное + Комментарий + Переслать ❤️

Автор: Школа Лао Цзю — технология Big Millet.

Авторские права принадлежат автору. Для коммерческих перепечаток, пожалуйста, свяжитесь с автором для получения разрешения, а для некоммерческих перепечаток, пожалуйста, укажите источник.