Презентация на тему: Разбор задач: Жадные алгоритмы

Разбор задач: Жадные алгоритмы
Коровы – в стойла
Коровы – в стойла: Решение
1/3
Средняя оценка: 4.0/5 (всего оценок: 74)
Код скопирован в буфер обмена
Скачать (41 Кб)
1

Первый слайд презентации: Разбор задач: Жадные алгоритмы

Изображение слайда
2

Слайд 2: Коровы – в стойла

На прямой расположены стойла, в которые необходимо расставить коров так, чтобы минимальное расcтояние между коровами было как можно больше. Входные данные В первой строке вводятся числа  N   (2 <  N  < 10001) – количество стойл и  K   (1 <  K  <  N  ) – количество коров. Во второй строке задаются  N натуральных чисел в порядке возрастания – координаты стойл (координаты не превосходят 10 9 ) Выходные данные Выведите одно число – наибольшее возможное допустимое расстояние. Примеры входные данные 6 3 2 5 7 11 15 20 выходные данные 9

Изображение слайда
3

Последний слайд презентации: Разбор задач: Жадные алгоритмы: Коровы – в стойла: Решение

var a:  array  [1..10000]  of   longint ; n, k, L, R, m,  i,  cnt :  longint ; function  count(x:  longint ):  longint ; var i,  cnt,  prev :  longint ; begin cnt  := 1;  prev  := 1; for   i  := 2  to  n  do   begin if  (a[ i ] - a[ prev ] >= x)  then   begin prev  :=  i ; inc ( cnt ); end ; end ; count  :=  cnt ; end ; begin read ( n,  k ); for   i  := 1  to  n  do   begin read ( a [ i ]); end ; L := 0; R :=  a [ n ]; while  (L + 1 < R)  do   begin m  := (L + R)  div  2; cnt  :=  count ( m ); if  ( cnt < k)  then  R := m  else  L := m; end ; writeln ((L + R)  div  2); end.

Изображение слайда