1871. Белка и бамбук

Белка решила отправиться в кругосветное путешествие. Попав в тропики, она обнаружила, что жёлуди находить стало труднее. Зато она нашла отличный стебель бамбука, и теперь вместо того, чтобы каждый день таскать жёлуди по одному от одного дупла до другого, носит их с собой в бамбуке.

Бамбук – это трубка, один конец которой закрыт, а с другого конца можно класть или вынимать жёлуди. Диаметр трубки достаточно мал, поэтому если положить в неё жёлуди в определённом порядке, вынимать их можно только в обратном порядке.

Когда белка находит жёлудь, она сразу кладёт его в бамбук. Кроме того, время от времени голод заставляет белку достать один жёлудь из бамбука и съесть его; из-за устройства бамбука это будет тот из желудей в нём, который белка нашла позже всего.

Белка очень любит копить жёлуди в бамбуке. Поэтому каждый раз, когда приходится доставать из бамбука очередной жёлудь, она испытывает печаль. Однако мы знаем, как можно её утешить! Жёлуди характеризуются для белки качеством – целым числом от 1 до 10⁶. Когда белка достала очередной жёлудь, ей будет приятно знать, каково максимальное значение качества для всех желудей, которые в бамбуке ещё остались. Ваша задача состоит в том, чтобы снабдить её такой информацией.

Вход. В первой строке ввода содержится одно целое число n – количество событий (1 ≤ n ≤ 10⁵). Каждая из следующих n строк содержит по числу, описывающему событие. Если число положительное, то оно означает, что белка нашла жёлудь и положила его в свой бамбук. Если же число равно нулю, то оно означает, что белка проголодалась и вынула один жёлудь из бамбука. Числа во входном файле целые и не превосходят 10⁶. Гарантируется, что после первого же запроса бамбук никогда не пуст.

Выход. Для каждого доставания жёлудя из бамбука выведите строку, содержащую одно целое число – максимальное значение качества для всех желудей, оставшихся в этот момент в бамбуке.

Пример входа	Пример выхода
8 3 2 4 0 4 3 0 0	3 4 3

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Промоделируем процесс перекладывания желудей. Бамбук представим в виде стека, где вместо качества текущего желудя запоминается максимальное значение качества желудей, уже находящихся в бамбуке (с учетом текущего желудя). Например, пусть вершина стека содержит значение a. Тогда если нам следует положить в бамбук желудь с качеством b, то в стек будет занесено значение max(a, b). При доставании желудя из бамбука мы можем отвечать на требуемый в условии задачи запрос за константное время – для этого достаточно вывести значение вершины стека.

Пример

Рассмотрим, как меняется состояние стека при моделировании перекладывания желудей, приведенных в примере. Жирным шрифтом в стеке выделено выводимое значение.

качество желудя	состояние стека	выводимое значение
-	(0) – инициализация	-
3	(0, 3)	-
2	(0, 3, 3)	-
4	(0, 3, 3, 4)	-
0	(0, 3, 3)	3
4	(0, 3, 3, 4)	-
3	(0, 3, 3, 4, 4)	-
0	(0, 3, 3, 4)	4
0	(0, 3, 3)	3

Реализация алгоритма

Объявим стек s, который будет хранить максимальное значение качества желудей, уже находящихся в бамбуке (с учетом текущего желудя).

stack<int> s;

Читаем входные данные. Инициализируем стек значением 0.

scanf("%d",&n);

s.push(0);

while(n--)

{

scanf("%d",&val);

В зависимости от значения val кладем желудь в бамбук или достаем его оттуда.

if (val > 0) s.push(max(val,s.top()));

else

{

s.pop();

printf("%d\n",s.top());

}

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Stack<Integer> s = new Stack<Integer>();

s.push(0);

while(n-- > 0)

{

int Value = con.nextInt();

if (Value > 0)

s.push(Math.max(Value,s.peek()));

else

{

s.pop();

System.out.println(s.peek());

}

}

}

}

Реализация при помощи собственного класса.

import java.util.*;

public class Main

{

public static class MutableInteger {

private int value;

public MutableInteger(int value) {

this.value = value;

}

public int intValue() {

return value;

}

public void set(int value) {

this.value = value;

}

public void increment() {

value++;

}

public String toString() {

return String.valueOf(value);

}

}

public static void main(String[] args) {

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Stack<MutableInteger> s = new Stack<MutableInteger>();

s.push(new MutableInteger(0));

while(n-- > 0) {

int Value = con.nextInt();

if (Value > 0)

s.push(new MutableInteger(Math.max(Value,s.peek().value)));

else {

s.pop();

System.out.println(s.peek());

}

}

}

}