Максимальное количество круглых зданий, которые можно охватить проводом длиной L

Дан массив arr[] размера N , представляющий диаметр N круглых зданий и прямой провод длиной L . Задача состоит в том, чтобы найти максимальную количество непрерывных зданий, которые может охватить провод, если он один раз обойдёт вокруг здания.

Примечание. Расстояние между каждым зданием составляет 1 единицу длины, поэтому требуется 1 единица длины. длина дополнительный, чтобы добраться от одной сборки до следующего здания.

Примеры:

Input: arr[] = {4, 1, 6}, L = 24
Output: 2
Explanation: 1 round of building will require  pi * d length of wire, where pi is 3.14159 and d is the diameter of circle.
For 1st building → 12.566 length of wire required, remaining wire→ 24-12.566=11.434 -1( to reach next building)=10.434
Similarly, for second building 3.141 length of wire required, remaining wire→ 10.434-3.141= 7.292 -1= 6.292 
For third building 18.849, which is > remaining wire i.e, 18.849>6.292
Therefore, Maximum of 2 building can be covered.

Input: arr[] = {2, 5, 3, 4}, L = 36
Output: 3

Подход: Идея состоит в том, чтобы использовать жадный подход. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные curr_sum, start, curr_count, max_count для вычисления текущей суммы элементов, текущего количества, начального индекса текущего подмассива и максимального количества покрытых зданий.
• Пройдите массив для i в диапазоне [0, N – 1],
  • Требуется обновить текущую сумму длины проводов, curr_sum += arr[i] * 3.14
  • Если fi больше 0, увеличивается curr_sum на 1.
  • Если curr_sum ≤ L . Увеличить curr_count на 1
  • В противном случае исключить arr[start] из текущей группы
    • Обновить curr_sum = curr_sum – ((double)arr[start] * 3.14)
    • Уменьшить curr_sum на 1
    • Увеличить начальный указатель на 1
    • Уменьшить curr_count на 1
• Обновить max_count , т. е . max_count = max(curr_count, max_count).
• После выполнения вышеуказанных шагов выведите в качестве результата значение max_count .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(1)