Минимум дней для создания элементов массива со значением не менее K в сумме не менее X

Имея два целых числа X , K и два массива arr[] и R[] , каждый из которых состоит из N положительных целых чисел, где R[i] обозначает величину, на которую arr[i] увеличивается за один день, задача состоит в том, чтобы найти минимальное число дней, после которых сумма элементов массива, имеющих значение больше или равное K , становится не менее X .

Примеры:

Input: X = 100, K = 45, arr[] = {2, 5, 2, 6}, R[] = {10, 13, 15, 12}
Output: 4
Explanation:
Consider the following values of array after each day:

1. Day 1: After the day 1, all array element modifies to {12, 18, 17, 18}. The sum of elements having values >= K(= 45) is 0.
2. Day 2: After the day 2, all array element modifies to {22, 31, 32, 30}. The sum of elements having values >= K(= 45) is 0.
3. Day 3: After the day 3, all array element modifies to {32, 44, 47, 42}. The sum of elements having values >= K(= 45) is 47.
4. Day 4: After the day 4, all array element modifies to {42, 57, 62, 54}. The sum of elements having values >= K(= 45) is 57 + 62 + 54 = 167, which is at least X(= 100).

Therefore, the minimum number of days required is 4.

Input: X = 65, K = 10, arr[] = {1, 1, 1, 1, 3}, R[] = {2, 1, 2, 2, 1}
Output: 9

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

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

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

• Инициализируйте две переменные, скажем, low как 0 и high как X .
• Инициализируйте переменную, скажем, minDays , которая хранит минимальное количество дней.
• Повторяйте до тех пор, пока значение low не станет максимально высоким , и выполните следующие шаги:
  • Инициализируйте переменную mid как low + (high – low)/2 и переменную, скажем, sum как 0 , чтобы сохранить сумму элементов массива после среднего количества дней.
  • Перейдите массив arr[] с помощью переменной i и выполните следующие шаги:
    • Инициализируйте переменную temp как (arr[i] + R[i]*mid) .
    • Если значение temp не меньше K , прибавьте значение temp к сумме .
  • Если значение sum не меньше X , то обновите значение minDays до mid и значение high до (mid – 1) .
  • В противном случае обновите значение low до (mid + 1) .
• После выполнения вышеуказанных шагов выведите значение minDays как результирующее минимальное количество дней.

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

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