4035. Мороженое

Вдоль моря узкой полосой тянется пляж. В некоторых точках пляжа расположены ларьки с мороженым. В один прекрасный день не все мороженщики вышли на работу. Распределите мороженщиков по ларькам так, чтобы минимальное расстояние между мороженщиками было как можно больше. Так они меньше будут мешать друг другу.

Вход. В первой строке вводятся количество ларьков n (2 < n < 10001) и количество мороженщиков k (1 < k < n), вышедших на работу. Во второй строке заданы n натуральных чисел в порядке возрастания – координаты ларьков (координаты не превосходят 10⁹).

Выход. Выведите одно число – минимальное расстояние между соседними ларьками в оптимальной расстановке.

Пример входа	Пример выхода
5 3 1 2 3 100 1000	99

РЕШЕНИЕ

бинарный поиск

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

Минимальное расстояние d между соседними ларьками в оптимальной расстановке будем искать бинарным поиском, начиная с интервала [0; 10⁹].

Зафиксируем значение d и выясним, можно ли рассадить мороженщиков по ларькам требуемым образом. В первый (самый левый) ларек посадим продавца. Второго продавца посадим в ларек, находящийся на расстоянии не меньшем d от первого. И так далее. Если всех мороженщиков удалось рассадить по ларькам, то значение d можно попробовать увеличить. Если рассадка продавцов не удалась, то уменьшаем d.

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

Объявим константы: максимальное количество ларьков MAX и плюс бесконечность INF. Координаты ларьков будем хранить в массиве m.

#define MAX 10001

#define INF 1000000000

int m[MAX];

Функция Check(Value) проверяет, можно ли рассадить продавцов мороженого по ларькам так, чтобы расстояние между ними было не меньше Value. Сделать это можно так. Садим первого продавца в первый ларек. Далее ищем ларек, который находится от первого на расстоянии, не меньшем Value. Садим в него второго продавца. И так далее, пока не рассадим всех продавцов. В переменной stall подсчитываем количество ларьков, в которые удалось посадить продавцов. Если рассадить k мороженщиков по ларькам не удастся (stall < k), то функция Check возвращает 0 (иначе 1).

int Check(int Value)

{

int i, stall = 1, len = 0;

for(i = 1; i < n; i++)

{

len += m[i] - m[i-1];

if (len >= Value) len = 0, stall++;

}

return stall >= k;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&n,&k);

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

scanf("%d",&m[i]);

Поскольку k < n, то всегда существует такое расстояние между соседними ларьками, при котором можно рассадить мороженщиков по ларькам. Пусть искомое минимальное расстояние находится в промежутке [Left; Right], изначально представляя собой интервал [0; 10⁹].

Left = 0; Right = INF;

while (Left < Right)

{

int Middle = (Left + Right) / 2;

if (Check(Middle)) Left = Middle + 1; else Right = Middle;

}

Выводим искомое минимальное расстояние.

printf("%d\n",Left-1);