Агрессивные коровы

Question

Агрессивные коровы

Рейтинг: 4Ответов: 1Опубликовано: 08.05.2011

Помогите найти оптимальное решение задачи (спортивное программирование):

ФД построил новый длинный амбар с 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.

алгоритм

Источник: Stack Overflow на русском

Answer 1

▲ 3Принят

ПРИДУМАЛ! решение за 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.

Агрессивные коровы

Ответы