Codeforces Round 939 (Div. 2) |
---|
Закончено |
Вы и Нина играете в карточную игру. Для игры используется колода из $$$2n$$$ карт. На каждой карте написано целое число от $$$1$$$ до $$$n$$$, и каждое из чисел от $$$1$$$ до $$$n$$$ встречается ровно на $$$2$$$ картах. Кроме того, есть стол, на который размещаются карты во время игры (в начале игры стол пустой).
В начале игры эти $$$2n$$$ карты распределяются между вами и Ниной так, что каждый игрок получает по $$$n$$$ карт.
После этого вы и Нина поочередно делаете суммарно $$$2n$$$ ходов, т. е. каждый делает по $$$n$$$ ходов, начиная с вас. На каждом ходу:
Обратите внимание, что ходы делаются публично: каждый игрок может видеть все карты на столе в каждый момент времени.
Нина очень умная, поэтому она всегда выбирает карты оптимальным образом, чтобы максимизировать свой счет в конце игры (после $$$2n$$$ раундов). Если у нее есть несколько оптимальных ходов, она выбирает ход, который минимизирует ваш счет в конце игры.
Более формально, Нина всегда делает ходы оптимальным образом, чтобы в первую очередь максимизировать свой счет в конце игры и во вторую очередь минимизировать ваш счет в конце игры.
Пусть в начале игры числа на ваших картах — $$$a_1, a_2, \ldots, a_n$$$. Какое максимальное количество очков вы можете получить, делая свои ходы оптимальным образом?
В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество карт, которые вы и Нина получаете в начале игры.
Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — числа на картах в вашей руке. Гарантируется, что каждое целое число от $$$1$$$ до $$$n$$$ встречается в последовательности $$$a_1, a_2, \ldots, a_n$$$ не более $$$2$$$ раз.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого тестового случая выведите одно целое число: максимальное количество очков, которое вы можете получить.
541 1 2 387 4 1 2 8 8 5 587 1 4 5 3 4 2 631 2 311
1 2 1 0 0
В первом наборе входных данных на ваших картах написаны числа $$$1$$$, $$$1$$$, $$$2$$$ и $$$3$$$. На картах Нины написаны числа $$$2$$$, $$$3$$$, $$$4$$$ и $$$4$$$. Возможный ход игры:
В конце игры вы набрали $$$1$$$ очко, а Нина $$$3$$$. Можно показать, что вы не можете набрать больше $$$1$$$ очка, если Нина играет оптимальным образом, поэтому ответ $$$1$$$.
Во втором тестовом случае, если оба игрока играют оптимальным образом, вы набираете $$$2$$$ очка, а Нина — $$$6$$$ очков.
Название |
---|