Агрессивные коровы [закрыт]

#алгоритм

        
             
                
                    
                        
                            Закрыт. Этот вопрос не по теме. Ответы на него в данный
момент не принимаются.
                            
                        
                    
                
                            
                                
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Переформулируйте вопрос,
чтобы он соответствовал тематике «Stack Overflow на русском».
                        
                        Закрыт 2 года назад.
                                                                                
           
                
        
Помогите найти оптимальное решение задачи (спортивное программирование):

ФД построил новый длинный амбар с N (2 <= N <= 100,000) стойлами.
Стойла расположены вдоль прямой линии на позициях x1,...,xN
(0 <= xi <= 1,000,000,000).
Его C (2 <= C <= N) коровам не нравится такой амбар и они становятся
агрессивными при установке их в стойла. Чтобы избежать прямых
столкновений, ФД хочет назначить коровам стойла так, чтобы минимальное
расстояние между любыми двумя из них было максимальным насколько это
возможно.
Каково это минимальное расстояние?
Формат ввода:

Строка 1: Два разделенных пробелом целых числа N и C
Строки 2..N+1: Строка i+1 содержит целые числа - места расположения стойл - xi

Пример ввода:
5 3
1
2
8
4
9

OUTPUT FORMAT:

Строка 1: Одно целое число - максимальное минимальное расстояние

Пример вывода:
3
Пояснения к выводу.
ФД может расставить 3 своих коровы в стойла в позициях 1, 4 и 8, в результате чего
получиться минимальное расстояние 3.
    

Ответы

Ответ 1

ПРИДУМАЛ!
решение за NlogN.
отсортируем все позиции по возрастанию (NlogN - qsort).
затем будем делать дихотомию по ответу (если можно так сказать), т. е. дихотомией
перебираем возможный ответ M (за всего log(10^9) ~ 35 шагов) и пробуем расставить максимальное
(не из условия а вообще максимальное) количество коров, чтобы расстояние между соседними
не превышало M. (за линейное время - количество стойл 10^5). Если расставили больше
коров, чем надо, то увеличиваем нижнюю границу дихотомии (ищем расстояние больше),
иначе уменьшаем верхнюю(мы не сможем расставить требуемое количество коров следовательно,
делаем верхнюю границу приближенного ответа меньше).
@gecube:

А теперь бы увидеть код и погонять его
:-)

легко ))) (Простите за pascal, просто мне нравиться решать задачи именно в нём)
const
        maxN     = 111111;

var
        i,n,c,j,count,cur               : longint;

        a                               : array [1..maxN] of longint;

        l,r,m                           : longint;

        ans                             : longint;

procedure swap(var w1,w2 : longint);
        var
                temp : longint;
        begin
                temp := w1; w1 := w2; w2 := temp;
        end;

procedure qsort(left,right : longint);
        var
                i,j,key : longint;
        begin
                i := left; j := right;
                key := a[(i + j) shr 1];
                repeat
                        while (a[i] < key) do inc(i);
                        while (a[j] > key) do dec(j);
                        if (i <= j) then begin
                                swap(a[i],a[j]);
                                inc(i); dec(j);
                        end;
                until i>j;
                if (i < right) then qsort(i,right);
                if (j > left)  then qsort(left,j);
        end;

begin
        readln(n,c);
        for i := 1 to n do begin
                read(a[i]);
                if a[i] > r then r := a[i];
        end;

        qsort(1,n);

        while l < r do begin
                m := (l + r + 1) shr 1;

                count := 1;
                cur := a[1];
                for i := 2 to n do
                        if a[i] - cur < m
                                then
                                        continue
                                else begin
                                        cur := a[i];
                                        inc(count);
                                end;

                if count >= c
                        then begin
                                l := m;
                                if count >= c
                                        then
                                                ans := m;
                        end
                        else begin
                                r := m-1;
                        end;
        end;

        writeln(ans);

end.


Ответ 2

Самое простое: рассмотреть все варианты размещения коров. 
Т.е. для примера с 3 коровами и 5 стойлами:
1 2 8, 1 2 4, 1 2 9, 1 8 4, 1 8 9, 1 4 9, 2 8 4, 2 8 9, 2 4 9, 8 4 9.
Получается всего лишь 10 вариантов (сочетание из 5 по 3 = 5!/(3!*(5-3)!)).
Далее не проблема рассчитать для каждого случая минимальное расстояние между коровами
и сохранить его в переменной. Ну, а далее просто ищем сравниваем текущее минимальное
расстояние с максимальным найденным.
PS: еще пара прикидок. Первая - минимальное расстояние может быть максимально при
максимальной длине отрезка между первой коровой и последней. Т.е. выгодно выбрать два
стойла с минимальной абсолютной координатой и с максимальной. Хотя не факт, что это
работает всегда. Вторая - наихудший вариант с точки зрения производительности для полного
перебора - какое-то среднее кол-во коров (где-то половина от кол-ва стойл). Очевидно,
что если кол-во стойл = кол-ву коров, то задача решена сразу :-) И когда 2 коровы,
то тоже все ясно. Третья - вероятно имеет смысл отсортировать стойла по возрастанию
координат. Также ясно, что может быть вариант, когда два стойла имеют одну и ту же
координату. Хотя вряд ли он корректен.
PPS:

ФД может расставить 3 своих коровы в стойла в позициях 1, 4 и 8, в результате чего
получиться минимальное расстояние 3.

При варианте 1,4,9 получаются расстояния 3 и 5, что всяко лучше, чем 3 и 4.


Ответ 3

Полагаю, что это задача на динамическое программирование. Начинаем перебирать возможные
ответы, начиная с максимума и в цикле решаем задачи расставить бешеных коров на расстоянии
друг от друга не меньше, чем наше фиксированное число. Предположив размещение очередной
бешеной коровы, начинаем решать эту же задачу, но с уменьшенной сложностью для оставшихся
коров на оставшихся участках. При этом рассматриваем только те варианты, которые потенциально
могут привести к решению (а их гораздо меньше, чем полный перебор). Как только коров
удалось расставить - ответ готов. Теоретически можно хешировать промежуточные результаты
для большей эффективности, но боюсь, это потребует слишком много памяти.