Быстрое питание
Фастфуд-сеть McBurger включает n ресторанов, расположенных вдоль автострады. Недавно владельцы решили построить k складов (k ≤ n), каждый из которых будет размещаться на базе одного из ресторанов (в том же здании, что и ресторан). Каждый склад будет обеспечивать продуктами ресторан, в здании которого он находится, а также некоторые другие рестораны, для которых этот склад будет являться ближайшим. Требуется написать программу, которая определит оптимальное расположение складов. Критерий оптимальности: сумма расстояний от каждого ресторана до ближайшего к нему склада должна быть наименьшей. Входные данные Во входных данных содержится описание нескольких фастфуд-сетей. Каждое описание начинается со строки, содержащей два целых числа n и k, где n – число ресторанов, k – число складов (1 ≤ n ≤ 200, 1 ≤ k ≤ n). Затем идут n строк, содержащих по одному целому числу – позиции di ресторанов от начала автострады в порядке возрастания. Все позиции лежат в диапазоне от -100000 до 100000. Входные данные заканчивается, когда n = k = 0. Выходные данные Для каждой фастфуд-сети выведите одно целое число – минимально возможную сумму расстояний от каждого ресторана до ближайшего к нему склада. Пример Входные данные 6 3 5 6 12 19 20 27 0 0 Выходные данные 8 | |||||||
|