Codeforces Round 979 (Div. 2) |
---|
Закончено |
Исследуя джунгли, вы наткнулись на редкого орангутана с галстуком-бабочкой! Вы пожали орангутану руку и предложили ему немного еды и воды. В ответ...
Орангутан подарил вам массив $$$a$$$ длины $$$n$$$. Используя $$$a$$$, вы построили два массива $$$b$$$ и $$$c$$$, каждый из которых будет содержать $$$n$$$ элементов, следующим образом:
Определим счёт массива $$$a$$$ как $$$\sum_{i=1}^n c_i - b_i$$$ (т.е. сумму $$$c_i - b_i$$$ по всем $$$1 \leq i \leq n$$$). Прежде чем вычислять счёт, вы можете переставить элементы $$$a$$$ в любом порядке.
Найдите максимальный счёт, который вы можете получить, если оптимально переставите элементы $$$a$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$) — количество элементов в $$$a$$$.
Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора входных данных выведите максимальный счёт, который вы можете получить.
316937 6 551 1 1 2 2
0 4 4
В первом наборе входных данных нет другого способа переставить элементы $$$a$$$. Таким образом, $$$b = [69]$$$ и $$$c = [69]$$$. Единственный возможный счёт — $$$69 - 69 = 0$$$.
Во втором наборе входных данных можно переставить элементы $$$a$$$ так: $$$[7, 5, 6]$$$. Тогда $$$b = [7, 5, 5]$$$ и $$$c = [7, 7, 7]$$$. Счёт в этом случае будет равен $$$(7 - 7) + (7 - 5) + (7 - 5) = 4$$$. Можно показать, что это максимально возможный счёт.
Название |
---|