Шеф Монокарп только что поставил $$$n$$$ блюд на плиту. Он знает, что оптимальное время готовки $$$i$$$-го блюда равно $$$t_i$$$ минут.
В любую положительную целую минуту $$$T$$$ Монокарп может снять не более одного блюда с плиты. Если достать $$$i$$$-е блюдо в некоторую минуту $$$T$$$, то его испорченность будет равна $$$|T - t_i|$$$ — модуль значения разности между $$$T$$$ и $$$t_i$$$. Как только блюдо снято с плиты, его уже нельзя поставить обратно.
Монокарп должен снять все блюда с плиты. Какую минимальную суммарную испорченность он может получить?
В первой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 200$$$) — количество наборов входных данных.
Затем идут $$$q$$$ наборов входных данных.
В первой строке набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 200$$$) — количество блюд на плите.
Во второй строке набора входных данных записаны $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_i \le n$$$) — оптимальное время готовки каждого блюда.
Сумма $$$n$$$ по всем $$$q$$$ наборам входных данных не превосходит $$$200$$$.
На каждый набор входных данных выведите одно целое число — минимальную суммарную испорченность блюд, которую может получить Монокарп, когда снимет все блюда с плиты. Помните, что Монокарп может снимать блюда только в положительные целые минуты и не более одного в минуту.
6 6 4 2 4 4 5 2 7 7 7 7 7 7 7 7 1 1 5 5 1 2 4 3 4 1 4 4 4 21 21 8 1 4 1 5 21 1 8 21 11 21 11 3 12 8 19 15 9 11 13
4 12 0 0 2 21
В первом наборе входных данных Монокарп может снять блюда в минуты $$$3, 1, 5, 4, 6, 2$$$. Тогда суммарная испорченность будет равна $$$|4 - 3| + |2 - 1| + |4 - 5| + |4 - 4| + |6 - 5| + |2 - 2| = 4$$$.
Во втором наборе входных данных Монокарп может снять блюда в минуты $$$4, 5, 6, 7, 8, 9, 10$$$.
В третьем наборе входных данных Монокарп может снять блюдо в минут $$$1$$$.
В четвертом наборе входных данных Монокарп может снять блюда в минуты $$$5, 1, 2, 4, 3$$$.
В пятом наборе входных данных Монокарп может снять блюда в минуты $$$1, 3, 4, 5$$$.
Название |
---|