Задача
Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:
| № | Транзакция | $i$ | Содержимое Черного Ящика после транзакции | Ответ |
| 1 | ADD(3) | 0 | 3 | |
| 2 | GET | 1 | 3 | 3 |
| 3 | ADD(1) | 1 | 1, 3 | |
| 4 | GET | 2 | 1, 3 | 3 |
| 5 | ADD(-4) | 2 | -4, 1, 3 | |
| 6 | ADD(2) | 2 | -4, 1, 2, 3 | |
| 7 | ADD(8) | 2 | -4, 1, 2, 3, 8 | |
| 8 | ADD(-1000) | 2 | -1000, -4, 1, 2, 3, 8 | |
| 9 | GET | 3 | -1000, -4, 1, 2, 3, 8 | 1 |
| 10 | GET | 4 | -1000, -4, 1, 2, 3, 8 | 2 |
| 11 | ADD(2) | 4 | -1000, -4, 1, 2, 2, 3, 8 |
Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:
- $A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
- $u_1, \ u_2, \ldots, \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$
Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.
Входные данные
Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.
Выходные данные
Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.
Тесты
| Входные данные | Выходные данные |
|
7 4 3 1 -4 2 8 -1000 2 1 2 6 6 |
3 3 1 2 |
|
8 3 5 8 3 7 3 5 7 0 2 3 3 |
5 5 8 |
|
10 4 6 3 7 3 8 4 7 4 6 15 4 6 8 9 |
3 3 4 4 |
|
5 5 1 2 3 4 5 1 2 3 4 5 |
1 2 3 4 5 |
|
11 5 4 6 8 9 5 3 6 8 10 12 13 6 7 8 9 10 |
3 4 5 6 6 |
Код программы
|
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 |
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Map; import java.util.Scanner; import java.util.TreeMap; public class Main { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int[] nums = new int[m]; for(int i = 0; i < m; i++){ nums[i] = sc.nextInt(); } TreeMap<Integer, Integer> blackBox = new TreeMap<>(); blackBox.put(Integer.MAX_VALUE, 1); int size = 1; int curKey = Integer.MAX_VALUE; int curValue = 1; int curPosition = 0; for(int i = 0; i < n; i++){ int req = sc.nextInt(); for(int j = size - 1; j < req; j++){ if (blackBox.containsKey(nums[j])) { blackBox.put(nums[j], blackBox.get(nums[j]) + 1); if (curKey == nums[j]) { curValue++; } } else { blackBox.put(nums[j], 1); } if(nums[j] < curKey) { if (curPosition == 0) { Map.Entry<Integer, Integer> curEnrty= blackBox.lowerEntry(curKey); curKey = curEnrty.getKey(); curValue = curEnrty.getValue(); curPosition = curValue - 1; } else { curPosition--; } } } size = req + 1; System.out.println(curKey); if (curPosition == curValue - 1) { Map.Entry<Integer, Integer> curEnrty = blackBox.higherEntry(curKey); curKey = curEnrty.getKey(); curValue = curEnrty.getValue(); curPosition = 0; } else { curPosition++; } } } } |
Решение задачи
В следствие того, что в JCF нет мультисета, реализуем необходимые нам его функции (а именно итерирование) на базе TreeSet, ключами которого будут уникальные значения, хранящиеся в черном ящике, а значениями — количество раз, которое это значение содержится в черном ящике. При чтении очередного запроса добавляем соответствующие элементы в черный ящик, итерируясь вниз в случае добавления меньшего элемента чем текущий, и итерируемся вверх после каждого запроса.
Ссылки
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone