Codeforces Round 858 (Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$ длины $$$n$$$. Цена массива $$$a$$$ — это MEX$$$^{\dagger}$$$ массива $$$[a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]$$$. Найдите минимальную цену $$$a$$$, если в нём разрешается переставлять элементы массива $$$a$$$ местами. Обратите внимание, что вам не нужно искать массив $$$a$$$, на котором достигается минимальная цена.
$$$^{\dagger}$$$ MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$2\le n\le 2\cdot10^5$$$).
Вторая строка каждого набора содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2\cdot 10^5$$$).
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите минимальную цену $$$a$$$ после перестановки элементов $$$a$$$ в любом порядке.
320 030 0 181 0 0 0 2 0 3 0
1 0 1
В первом наборе входных данных оптимальной является перестановка $$$a$$$, равная $$$[0,0]$$$, ценой этого массива является MEX массива $$$[0+0]=[0]$$$, равный $$$1$$$.
Во втором наборе оптимальной является перестановка $$$a$$$ равная $$$[0,1,0]$$$, ценой этого массива является MEX массива $$$[0+1,1+0]=[1,1]$$$, равного $$$0$$$.
Название |
---|