Codeforces Round 936 (Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$ из $$$n$$$ целых чисел.
Будем называть медианой массива $$$q_1, q_2, \ldots, q_k$$$ число $$$p_{\lceil \frac{k}{2} \rceil}$$$, где $$$p$$$ — отсортированный по неубыванию массив $$$q$$$. Например, медиана массива $$$[9, 5, 1, 2, 6]$$$ это $$$5$$$, так как в отсортированном массиве $$$[1, 2, 5, 6, 9]$$$ число с индексом $$$\lceil \frac{5}{2} \rceil = 3$$$ это $$$5$$$, а медиана массива $$$[9, 2, 8, 3]$$$ это $$$3$$$, так как в отсортированном массиве $$$[2, 3, 8, 9]$$$ число с индексом $$$\lceil \frac{4}{2} \rceil = 2$$$ это $$$3$$$.
За одно действие вам разрешается выбрать целое число $$$i$$$ ($$$1 \le i \le n$$$) и увеличить $$$a_i$$$ на $$$1$$$.
Ваша задача найти минимальное количество действий, за которое можно увеличить медиану массива.
Обратите внимание, что в массиве $$$a$$$ необязательно все числа различны.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — сам массив $$$a$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных в отдельной строке выведите одно целое число — минимальное количество действий за которое можно увеличить медиану массива.
832 2 847 3 3 11100000000055 5 5 4 562 1 2 3 1 421 221 145 5 5 5
1 2 1 3 2 1 2 3
В первом наборе входных данных можно применить одну операцию к первому числу и получить массив $$$[3, 2, 8]$$$, у этого массива медиана равна $$$3$$$, так как это число с индексом $$$\lceil \frac{3}{2} \rceil = 2$$$ в отсортированном по неубыванию массиве $$$[2, 3, 8]$$$. У изначального массива $$$[2, 2, 8]$$$ медиана равна $$$2$$$, так как это число с индексом $$$\lceil \frac{3}{2} \rceil = 2$$$ в отсортированном по неубыванию массиве $$$[2, 2, 8]$$$. Таким образом медиана увеличилась ($$$3 > 2$$$) всего за одно действие.
В четвертом наборе входных данных можно применить по одной операции к числам с индексами $$$1, 2, 3$$$ и получить массив $$$[6, 6, 6, 4, 5]$$$, у этого массива медиана равна $$$6$$$, так как это число с индексом $$$\lceil \frac{5}{2} \rceil = 3$$$ в отсортированном по неубыванию массиве $$$[4, 5, 6, 6, 6]$$$. У изначального массива $$$[5, 5, 5, 4, 5]$$$ медиана равна $$$5$$$, так как это число с индексом $$$\lceil \frac{5}{2} \rceil = 2$$$ в отсортированном по неубыванию массиве $$$[4, 5, 5, 5, 5]$$$. Таким образом медиана увеличилась ($$$6 > 5$$$) за три действия. Можно показать, что это минимальное возможное количество действий.
В пятом наборе входных данных можно применить по одной операции к числам с индексами $$$1, 3$$$ и получить массив $$$[3, 1, 3, 3, 1, 4]$$$, у этого массива медиана равна $$$3$$$, так как это число с индексом $$$\lceil \frac{6}{2} \rceil = 3$$$ в отсортированном по неубыванию массиве $$$[1, 1, 3, 3, 3, 4]$$$. У изначального массива $$$[2, 1, 2, 3, 1, 4]$$$ медиана равна $$$2$$$, так как это число с индексом $$$\lceil \frac{6}{2} \rceil = 3$$$ в отсортированном по неубыванию массиве $$$[1, 1, 2, 2, 3, 4]$$$. Таким образом медиана увеличилась ($$$3 > 2$$$) за два действия. Можно показать, что это минимальное возможное количество действий.
Название |
---|