В недавней статье мы рассматривали такую структура данных как стек. Если вы не знаете что такое стек, то обязательно перейдите по ссылке и почитайте, потому что сегодня мы разберем решение одной интересной задачи с сайта codeforces.com с использованием реализованного ранее нами стека. Вот условие задачи:

Описание алгоритма решения задачи

Из условия задачи можно заметить следующую закономерность: каждый новый экстраверт сядет к интроверту, который сидит на сиденье с самой большой шириной. Значит, что могут быть еще интроверты в автобусе, и гарантировано что ширина их сидений меньше. Это типичный стек. Идея для решения в следующем. Пойдем по порядку входных данных. Сначала мы получаем число n и создаем объект класса Stack. Далее ширины сидений мы запишем в map по принципу (номер ряда -> ширина). Затем нам необходимо отсортировать ее (мапу) по значению и последовательно сложить в стек номера рядов, причем на самом верху будет номер с наименьшей шириной. Последовательность из 0 и 1 (интровертов и экстравертов, которые будут заходить в автобус мы  сложим в массив. Рассмотрим пример, в котором n=3, ширины рядов: 8 4 5, а последовательность людей: 0 0 1 1 0 1. Предложенная раскладка данных будет выглядеть так:

Последовательность захода людей в автобус

Отлично. Теперь нам необходимо создать второй стек, который будет тоже иметь размерность n, но будет пустым. После мы начинаем последовательно извлекать из массива людей (элементы 0 и 1) и проводить два типа операций в зависимости от того, кто зашел интроверт или экстраверт:

1. • Зашел интроверт 0.  Так как зашел интроверт и нам известно, что он сядет на свободный ряд с самой минимальной шириной. Значит мы выводим на консоль и извлекаем элемент из стека с ширинами, и кладем его в пустой, заранее подготовленный стек.

   

   • Зашел экстраверт 1. Экстраверт сядет к интроверту, причем к тому, который сидит на максимально широком ряду. Из второго стека, мы извлекаем элемент и выводим его на консоль. Это справедливо, потому что если заходили интроверты, то ряд с максимальной шириной окажется на верху стека. Соответственно, если зайдет еще один экстраверт, то он так же сядет с интровертом, у которого ширина ряда максимальная в силу принципа работы нашего стека.

   
   Реализация алгоритма на языке Java представлена ниже:
   

   import java.util.*; public class Solution { static class Stack { private int size; // Размер стека private int top; // индекс вершины private int[] stack; // сам стек public Stack(int size) { // конструктов this.size = size; top = -1; // -1 потому что стек пуст stack = new int[size]; // иницилизазция } public int pop() { // извлечение элемента return stack[top--]; } public int peek() { // получение элемента return stack[top]; } public void push(int a) { // вставка элемента stack[++top] = a; } public boolean isEmpty() { // проверка путой ли стек return (top == -1); } public boolean isFull() { // проверка полон ли стек return (top == size - 1); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); Map<Integer, Integer> map = new HashMap<>(); Stack stackSeatWidths = new Stack(n); // создаем стек где будут номера ширин рядов for (int i = 1; i <= n; i++) { map.put(i, scanner.nextInt()); // заполняем map с ширинами, где ключ - номер ряда } map.entrySet() .stream() // с помощью stream API сортируем map по значениям .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed()) .forEach(m -> stackSeatWidths.push(m.getKey())); // и складываем в стек упорядоченные по ширине номера сидений String str = scanner.next(); char[] b = str.toCharArray(); Stack stackSeatWidths2 = new Stack(b.length); // создаем второй стек для номеров ширин for (int i = 0; i < n * 2; i++) { if (b[i] == '0') { // если интроверт выводим значение из стека мест System.out.print(stackSeatWidths.peek() + " "); stackSeatWidths2.push(stackSeatWidths.pop()); //кладем вв второй стек } if (b[i] == '1') // если экстраверт, выводим значение из второго стека System.out.print(stackSeatWidths2.pop() + " "); } } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

   import java.util.*;   public class Solution {       static class Stack {         private int size;          // Размер стека         private int top;           // индекс вершины         private int[] stack;       // сам стек           public Stack(int size) {   // конструктов             this.size = size;             top = -1;              // -1 потому что стек пуст             stack = new int[size]; // иницилизазция         }           public int pop() {         // извлечение элемента             return stack[top--];         }           public int peek() {        // получение элемента             return stack[top];         }           public void push(int a) { // вставка элемента             stack[++top] = a;         }           public boolean isEmpty() { // проверка путой ли стек             return (top == -1);         }           public boolean isFull() {  // проверка полон ли стек             return (top == size - 1);         }       }       public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         int n = scanner.nextInt();         Map<Integer, Integer> map = new HashMap<>();         Stack stackSeatWidths = new Stack(n);      // создаем стек где будут номера ширин рядов         for (int i = 1; i <= n; i++) {             map.put(i, scanner.nextInt());         // заполняем map с ширинами, где ключ - номер ряда         }         map.entrySet()                 .stream()                         // с помощью stream API сортируем map по значениям                 .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed())                 .forEach(m -> stackSeatWidths.push(m.getKey()));         // и складываем в стек упорядоченные по ширине номера сидений         String str = scanner.next();         char[] b = str.toCharArray();         Stack stackSeatWidths2 = new Stack(b.length);    // создаем второй стек для номеров ширин         for (int i = 0; i < n * 2; i++) {             if (b[i] == '0') {                      // если интроверт выводим значение из стека мест                 System.out.print(stackSeatWidths.peek() + " ");                 stackSeatWidths2.push(stackSeatWidths.pop()); //кладем вв второй стек             }             if (b[i] == '1')                            // если экстраверт, выводим значение из второго стека                 System.out.print(stackSeatWidths2.pop() + " ");         }     } }