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

Опубликовано: 22 Сентября, 2022

Дан массив arr[] , состоящий из N целых чисел, и массив P[] , состоящий из M целых чисел, так что P[i] представляет результат, полученный за работу в i -й день . Задача состоит в том, чтобы найти минимальное количество дней, необходимое для работы, чтобы получить оценку не ниже arr[i] для каждого элемента массива arr[i] .

Примеры:

Input: arr[] = {400, 200, 700}, P[] = {100, 300, 400, 500, 600}
Output: 2 2 3 4 5
Explanation:
Following are the number of days required for each array elements:

  1. arr[0](= 400): To earn 400 points one has to work for first 2 days making the total points equal to 100 + 300 = 400(>= arr[0]).
  2. arr[1](= 200): To earn 200 points one has to work for first 2 days making the total points = 100 + 300 = 400(>= arr[1]).
  3. arr[2](= 700): To earn 700 points one has to work for first 3 days making the total points = 100 + 300 + 400 = 800(>= arr[2]).

Input: arr[] = {1400}, P[] = {100, 300}
Output: -1

Наивный подход: самый простой подход к решению проблемы — пройтись по массиву arr[] и для каждого элемента массива найти минимальный индекс массива P[] , чтобы сумма подмассива в диапазоне [0, i] была равной наименьший обр[i] .

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

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

  • Найдите массив суммы префиксов массива P[].
  • Пройдите по заданному массиву arr[] и выполните следующие шаги:
    • Найдите индекс первого элемента, большего, чем текущий элемент arr[i] в массиве P[] и сохраните его в переменной, скажем, index .
    • Если значение индекса равно -1 , то выведите -1 . В противном случае выведите значение (индекс + 1) в качестве результата для текущего индекса.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ