Устав города красноярска;doc

PRLADDU : DevuLand, Dinosaurs and Laddus
Легенда, описанная далее, переформулирована и упрощена переводчиком, чтобы читатель мог
лучше понять условие задачи. Оригинальную легенду вы можете прочитать на странице
задачи в контесте.
Условие:
Рассмотрим N деревень, расположенных друг за другом. Расстояние между двумя деревнями,
скажем, i-ой и j-ой есть |i-j|. В каждой из деревень находятся либо люди, либо динозавры.
Информация о них дана массивом D. Если D[i] >= 0, то в i-ой деревне находится D[i] людей,
иначе - -D[i] динозавров.
Гарантируется, что суммарное количество людей равняется суммарному количеству динозавров.
Требуется каждому человеку поставить в соответствие одного динозавра так, чтобы это
соответствие было взаимнооднозначным (то есть, каждому динозавру поставлен в соответствие
ровно один человек и каждый человек поставлен в соответствие ровно одному динозавру),
чтобы сумма расстояний между деревнями людей и поставленных им в соответствие динозавров
была минимальной.
Формат ввода:
Первая строка содержит целое число T – количество тестовых случаев. Далее следует T
описаний тестов.
Первая строка каждого описания содержит целое число N – количество деревень.
Вторая строка содержит N разделенных одиночными пробелами целых чисел – массив D,
описывающий деревни.
Формат вывода:
Для каждого тестового случая выведите минимальную возможную сумму расстояний.
Ограничения:
•
•
•
•
•
1 <= T <= 105
1 <= N <= 105
-104 <= Di <= 104
Сумма всех N в одном тестовом файле <= 106
Сумма всех Di равна нулю в каждом тестовом случае, что гарантирует равенство
количества людей и количества динозавров.
Примеры тестов:
Входные данные:
3
2
5 -5
2
-5 5
3
1 2 -3
1
Выходные данные:
5
5
4
Пояснение:
В первом тестовом примере, каждому жителю первой деревни поставлен в соответствие
динозавр из второй деревни.
Во втором тестовом примере, каждому жителю второй деревни поставлен в соответствие
динозавр из первой деревни.
В третьем тестовом примере каждому жителю второй деревни поставлен в соответствие
динозавр из третьей, и житель из первой деревни также имеет динозавра их третьей деревни
поставленным себе в соответствие. Получаем сумму расстояний |2-3| + |2-3| + |1-3| = 4.
1