Минимизируйте K, чтобы человек A съел не менее ceil(N/(M + 1)) конфет на основе заданных правил.

Имея N конфет, M человек и массив arr[] из M положительных целых чисел, задача состоит в том, чтобы найти минимальное значение K , такое, что Человек A может потреблять в сумме не менее ceil из (N/(M + 1)) конфеты по следующим правилам:

• В первый ход Человек А съедает минимальное количество оставшихся конфет и К.
• В следующие M ходов каждый i ^-й человек в диапазоне [0, M-1] съедает пол arr[i] процента оставшихся конфет.
• Повторяйте вышеуказанные шаги, пока не останется конфет.

Примеры:

Input: N = 13, M = 1, arr[] = {50}
Output: 3
Explanation:
For the value K as 3, the good share is the ceil of (13/2) = 7. Following are the turns that takes place:

1. Person A takes min(3,13)=3 candies. Therefore, the candies left = 13 – 3 = 10.
2. Person 0 takes arr[0](= 50)% of the 10 left candies, i.e., 5 candies. Therefore, the candies left = 10 – 5 = 5.
3. Person A takes min(3,5)=3 candies. Therefore, the candies left = 5 – 3 = 2.
4. Person 0 takes arr[0](= 50)% of the 2 left candies, i.e., 1 candies. Therefore, the candies left = 2 – 1 = 1.
5. Person A takes 1 candy. Therefore, the candies left = 1 – 1 = 0.

After the above turns, the candies taken by the person is 3 + 3 + 1 = 7, which is at least (N/(M + 1)) candies, i.e., 13/2 = 6.

Input: N = 13, M = 2, arr[] = {40, 50}
Output: 2

Наивный подход: самый простой подход к решению данной задачи — проверить для каждого количества конфет, которое получит человек А , все возможные значения K . Выполните следующие шаги, чтобы решить эту проблему:

• Найдите значение (N/(M + 1)) и сохраните его в переменной, скажем, good , поскольку это минимальное количество конфет, которое человек A хочет взять.
• Переберите все значения K в диапазоне [1, N] и выполните следующие шаги:
  • Для каждого значения K смоделируйте описанный выше процесс и подсчитайте общее количество конфет, которые получит человек А.
  • Если количество конфет не меньше значения good , то выйти из цикла. В противном случае продолжайте итерацию.
• После выполнения вышеуказанных шагов выведите в качестве результата текущее значение K.

Ниже приведена реализация вышеуказанного подхода:

Выход:

3

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

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

• Найдите значение (N/(M + 1)) и сохраните его в переменной, скажем, good , поскольку это минимальное количество конфет, которое человек A хочет взять.
• Инициализируйте две переменные, скажем, low и high как 1 и N соответственно.
• Повторяйте до тех пор, пока низкий уровень не станет меньше высокого , и выполните следующие шаги:
  • Найдите значение mid как (low + high)/2 .
  • Найдите минимальное количество конфет, взятых человеком А для значения K как среднего , моделируя процесс, упомянутый выше.
  • Если количество конфет, взятых человеком А , по крайней мере хорошее , обновите значение high до mid . В противном случае обновите значение low как (mid + 1) .
• После выполнения вышеуказанных шагов выведите значение high как результирующее минимальное значение K .

Ниже приведена реализация вышеуказанного подхода:

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