Задача. Школьная столовая
В школьной столовой есть круглые и квадратные булочки (0 и 1 соответственно). Ученики стоят в очереди и у каждого ученика есть свои предпочтения по выбору булочки.
Количество булочек равно количеству учеников. Булочки уложены стопкой.
Если ученик в начале очереди предпочитает булочку сверху стопки, то он может взять ее и выйти из очереди. В противном случае он снова переходит в конец очереди. Это продолжается до тех пор, пока ни один из учеников очереди не сможет взять свою любимую булочку.
- массив students, где students[i] - это предпочтение iго студента в типе булочки (students[0] - 1й ученик в очереди).
- массив buns, где buns[i] - тип булочки в стопке (buns[0] - это верхняя булочка в стопке).
Необходимо вернуть количество учеников, которые так и не смогут взять свою булочку из стопки.
students = [1,1,0,0] buns = [0,1,0,1] Output: 0
1. students = [1,1,0,0] buns = [0,1,0,1] 2. students = [1,0,0,1] buns = [0,1,0,1] 3. students = [0,0,1,1] buns = [0,1,0,1] ученик забирает булочку 4. students = [0,1,1] buns = [1,0,1] 5. students = [1,1,0] buns = [1,0,1] ученик забирает булочку 6. students = [1,0] buns = [0,1] 7. students = [0,1] buns = [0,1] последние 2 ученика забирают последние булочки
Разбор
Предоставим не самое оптимальное, но самое очевидное решение. Так как в задаче фигурируют 2 очереди, очередь учеников и очередь из булочек. Далее мы просто смоделируем сам процесс.
Создадим цикл по количеству учеников, в цикле проверим совпадение предпочтений, если нашли совпадение, то удаляем соотв.элементы из обоих очередей, в противном случае, обновляем очередь учеников и увеличиваем наш счетчик.