10041. Семья Вито

У Вито большая семья в Нью-Йорке. Он хочет поселиться на улице, суммарное расстояние от которой до улиц проживания его родственников минимальна.

Вход. Первая строка содержит количество тестов. Каждый тест задается одной строкой. Первое число в строке содержит число родственников n (0 < n < 500), за которым идут номера их улиц s₁, s₂, …, s_n (0 < s_i < 30000). Расстояние между улицами с номерами s_i и s_j равно d_ij = |s_i – s_j|. На одной улице могут проживать несколько родственников.

Выход. Для каждого теста вывести минимальное суммарное расстояние от улицы Вито до улиц его родственников.

Пример входа

3

2 2 4

3 2 4 6

3 3 1 7

Пример выхода

2
4
6

РЕШЕНИЕ

сортировка

Анализ алгоритма

Отсортируем номера их улиц n родственников. Нумерацию индексов улиц родственников будем вести с нуля: считаем, что входными номерами улиц являются s₀, s₁, …, s_n-1. Если Вито поселится на улице x, то суммарное расстояние от нее до родственников равно

f(x) = |x – s₀| + |x – s₁| + … + |x – s_n-1|

Минимум функции f(x) достигается при x = s_[n/2]. Таким образом, Вито должен поселиться на улице с номером s_[n/2]. Вычислим суммарное расстояние от улицы s_[n/2] до улиц s_i (1 £ i £ n) и выведем его.

Пример

Рассмотрим третий тест. Сортируем номера улиц: 1, 3, 7. Число улиц n равно 3. Считаем, что s₀ = 1, s₁ = 3, s₂ = 7. Номер улицы Вито равен s_[n/2] = s₁ = 3. Суммарное расстояние до родственников равно f(3) = |1 – 3| + |3 – 3| + |7 – 3| = 2 + 0 + 4 = 6.

Реализация алгоритма

В массиве m храним номера улиц родственников s_i. При этом m[i] = s_i+1,0 £ i £ n – 1_.

int m[500];

Для каждого теста вводим значения входных данных, сортируем номера улиц родственников (массив m). Вычислим сумму расстояний от оптимального номера улицы Вито с номером s_[n/2] до всех остальных улиц и выведем ее.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&m[i]);

sort(m,m+n);

for(s = i = 0; i < n; i++)

s += abs(m[n/2]-m[i]);

printf("%d\n",s);

}