Бинарный поиск Опции

[chappiiiiiiiiii]

Имеется N катушек с нитками. На первой из них A1 см ниток, на второй - A2 см,:, на N-ой - AN см. Для красивой вышивки требуется K штук кусков ниток равной длины. Требуется узнать какую наибольшую длину может иметь каждый из K кусков, если
1) нитки связывать нельзя, их можно только резать;
2) каждый из K кусков имеет длину равную целому числу сантиметров.

Входные данные
В первой строке входного файла записано два целых числа N и K (1 <= N, K <= 1000). Далее, во второй строке, следует N целых чисел A1, A2, ...,AN (1 <= Ai <= 100000, для всех i=1,..,N), разделенных пробелами и/или переводами строк.

Выходные данные
Выведите единственное целое число - наибольшую возможную длину каждого из K равных кусков (возможно, что ответ равен 0).

Пример

Ввод

2 5
2 4


Вывод

1

Как решить??? а то горит зачет.

[Shura]

А что именно не получается? Работа с файлами, подсчет кол-ва кусков, алгоритм бинарного поиска? Или может быть нужна программа целиком? Так это сюда: задачи на заказ.

[Гость]

А что именно не получается? Работа с файлами, подсчет кол-ва кусков, алгоритм бинарного поиска? Или может быть нужна программа целиком? Так это сюда: задачи на заказ.

Подсчет кол-во кусков.

[Shura]

Обычный поиск. Берешь число "p", равное максимальному элементу из А. Нацело делишь каждый элемент из А на "p". Результаты складываешь. Если сумма эта меньше, чем "к", значит эта длина (p) не подходит. Тогда уменьшаешь "p" на единицу и делаешь то же самое. И так до тех пор пока сумма эта не будет больше либо равна "k".
Бинарный поиск. Не врублюсь до конца, зачем он тут - только усложняется все... Делается примерно так же. По правилу бинарного поиска ищем первое число среди интервала 1..max (max - максимальный элемент из А), которое НЕ удовлетворяет условию "сумма >= k".

Сообщение отредактировано: Shura - 9.01.2006 20:23

[chapiiiiiiiiiii]

Обычный поиск. Берешь число "p", равное максимальному элементу из А. Нацело делишь каждый элемент из А на "p". Результаты складываешь. Если сумма эта меньше, чем "к", значит эта длина (p) не подходит. Тогда уменьшаешь "p" на единицу и делаешь то же самое. И так до тех пор пока сумма эта не будет больше либо равна "k".
Бинарный поиск. Не врублюсь до конца, зачем он тут - только усложняется все... Делается примерно так же. По правилу бинарного поиска ищем первое число среди интервала 1..max (max - максимальный элемент из А), которое НЕ удовлетворяет условию "сумма >= k".

спасибо.

[Shura]

Вот набросок с обычным поиском. К и N задаются вручную в теле программы.

Код

Uses
Crt;
var
a: Array [1..1000] of LongInt;
i,n,k,p: Word;
j,max,l,t: LongInt;

begin
Randomize;
ClrScr;
n:=10;
k:=15;
for i:=1 to n
do begin
     a[i]:=Random(20)+10;
     Write(a[i],' ')
    end;
writeLn;

max:=a[1];
for i:=2 to n
do if a[i] > max
    then max:=a[i];

j:=max+1;
repeat
  Dec(j);
  p:=0;
  for i:=1 to n
  do Inc(p,(a[i] div j))
until (j < 0)or(p >= k);

Write(j);
ReadLn

End.