Решение задачи на основе бинарного поиска по ответу

Question

Имеется задача:

На прямой дано N точек и число k. Вы должны покрыть точки с помощью k одинаковых по длине отрезков, причем требуется определить, какая минимальная длина отрезков подходит в задаче.

Например:

Если на прямой даны точки A=10, B=15, C=30, D=40 и k=2, то эти точки можно покрыть отрезками длины 10. Первый отрезок покрывает точки A и B, второй — C и D.
Если k=3, то эти же точки можно покрыть отрезками длины 5. Первый отрезок покрывает точки A и B, второй — C, третий D.
При k=4 ответ будет 0. Каждый из четырех отрезков покрывает одну из точек.

Для решения задачи используйте двоичный поиск по ответу. Отрезок длины 0 это самое маленькое возможное значение, а отрезок длины от первой точки до последней — самое большое, такой один отрезок гарантированно покроет все точки.

Идею бинарного поиска по ответу я понял, но как применить его к этой задаче не особо понятно, подскажите пожалуйста как реализовать данный алгоритм. По идеи нужно начинать от 0 и увеличивать размер отрезка, но при бинарном поиске происходит наоборот и отрезок уменьшается от максимального к минимальному, и не понятно как это решается.

Ну и не понятно как потом проверять подходит ли длина отрезка, как это реализовать тоже непонятно. Заранее спасибо за помощь.

Answer 1

Без ограничения общности можно считать, что 1) каждый из К отрезков начинается в одной из точек и 2) отрезки не перекрываются друг с другом

Я надеюсь, что эти утверждения понятны и не требует объяснений? Если нет - просто порисуйте на бумаге, мне это кажется довольно очевидным.

Тогда, следуя рекомендации задачи "использовать двоичный поиск" выбираем длину отрезка.

Теперь - вот он, алгоритм проверки возможности покрытия для данной длинны отрезка: Начинаем покрывать К такими отрезками все точки: "кладём" первый отезок, начиная его из первой точки. смотрим, сколько точек покрылось. "кладём" второй отрезок из первой точки, не покрытой первым отрезком. В конце -получаем результат, удалось ли покрыть все точки.

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

Answer 2

Предположим, что точек у нас всегда больше 0, и что они упорядочены. Тогда

Сначала напишем функцию, которая по данным точкам, k и длине отрезка, скажет, можно ли такими отрезками покрыть точки

private bool isLenRight(int[] points, int k, int len)
{       
    int end = points[0] + len;
    k--;
    for (int i = 0; i < points.Length; i++)
    {

        if (end < points[i])
        {
            k--;
            end = points[i] + len;
            if (k < 0) return false;
        }
    }
    
    return true; 
}

Далее все элементарно, самый обычный двоичный поиск

private int getLen(int[] points, int k)
{
    if (k >= points.Length) return 0;
    
    int min = 0; 
    int max = points[points.Length-1] - points[0];
    
    while(min != max)
    {
        int mid = min + (max - min) / 2;
        if (mid == max || mid == min) return max;

        if (isLenRight(points, k, mid)) max = mid;
        else min = mid;
    }
    
    return max; 
}

Проверяем

Console.WriteLine(getLen(new[] {10, 15, 30, 40}, 2));
Console.WriteLine(getLen(new[] {10, 15, 30, 40}, 3));
Console.WriteLine(getLen(new[] {10, 15, 30, 40}, 4));

Вывод

10
5
0

БЛОГ НА HUSL

Решение задачи на основе бинарного поиска по ответу

Ответы (2 шт):