5. Бинарный поиск по ответу. Рекурсия_Реализация

☰ Теория

Рассмотрим зададу "Провода"
Дано N отрезков провода длиной L1, L2, ..., LN сантиметров.
Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины,
выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.
Задача на оптимизацию, по набору от параметра K. Практическое решение задачи несложно, если применить 
метод Бинарного поиска по ответу (BSA). Суть метода в том, что

  1. Если можно разрезать на K кусков длины L, то можно разрезать и на K кусков меньшей длины
  2. Если нельзя разрезать на K кусков длины L, то нельзя разрезать и на K кусков большей длины
  3.  Количество вариантов ответа конечно (от 1 до максимальной длины отрезка)
  4.  Если зафиксировать длину отрезка L, то несложно найти KL - число кусков, которые можно получить.
Значит, если определить функция KL, то это будет монотонная функция, для которой несложно найти ответ с помощью
бинарного поиска
Решение задания можно организовать с помощью рекурсии  с использованием программ
  • auto solve(const vector <int> & D, M); - возвращающей количество отрезков длины M, которые можно получить из набора длин 
  • auto bsa(int L,int R, const vector <int> & D, int K) - возвращающий ответ на задание, где
    L - достижимое значение длины (инициализируем 1, если сумма длин всех отрезков не меньше K)
    R - значение длины, которое  нельзя получить (инициализируем  любым значение большим максимальной длины отрезка)
    D - набор длин отрезков
    K - количество отрезков которое надо получить 

Задача
Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0. 
Формат входных данных
В первой строке находятся числа N и K. В следующих N строках L1, L2, ..., LN, по одному числу в строке.

Ограничения 
  • 1 <= N <= 10 000,
  • 1 <= K <= 10 000,
  • 100 <= Li <= 10 000 000,
  • все числа целые.
Формат входных данных
Вывести одно число - полученную длину отрезков.
Примеры
№
Входные данные
Выходные данные
1
4 11
802
743
457
539
 
200
Для решения задачи реализуйте рекурсивный бинарный поиск по ответу (BSA)
Ваша задача дополнить представленный код (описание см. в теории)
Пояснение
Изменяйте только те строки, которые необходимо (помечено в комментариях)
 
Вставьте недостающие фрагменты кода
C++ 
#include <iostream>
#include <vector>

using namespace std; 
           
int main () {
   int L = 1, R = 0, K, n ;
   cin >> n >> K;
   vector <int> D(n);
   for (int i = 0; i < n; i++){
   cin >> D.at(i);
   if (R <= D.at(i)) {R = D.at(i) + 1;}
   } 
  if (solve(D, 1) <  K) {
  cout << 0; return 0; }
  auto ans = bsa(L, R, D, K);
  cout << ans;   return 0;}
     

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!