Помогите найти оптимальное решение задачи (спортивное программирование): ФД построил новый длинный амбар с 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.
Ответ
ПРИДУМАЛ!
решение за 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.
Комментариев нет:
Отправить комментарий