Минимальное количество индексов массива, которое необходимо выбрать, чтобы сумма набора была больше, чем сумма другого

Даны два массива arr[] и brr[] размера N и целое число K . Рассмотрим два множества A , изначально содержащее K , и B , изначально пустое. В каждой операции необходимо выбрать индекс. Для каждого выбранного индекса, скажем, i , arr[i] и brr[i] добавляются к B. Для каждого невыбранного индекса к A добавляется arr[i] . Задача состоит в том, чтобы найти минимальное количество индексов, которые необходимо выбрать, чтобы сумма B была больше суммы A . Если это невозможно сделать, то выведите -1.

Примеры:

Input: arr[] = {3, 2, 5, 6}, brr[] = {4, 4, 2, 3}, K = 12   
Output: 3
4 3 1
Explanation: Indices 2, 3 and 0 are selected. Sum of B = arr[0] + brr[0] + arr[2] + brr[2] + arr[3] + brr[3] = 3 + 4 + 5 + 2 + 6 + 3 = 23. Sum of A = K + arr[1] = 12 + 2 = 14.

Input: arr[] = {3, 2, 5, 6}, brr[] = {4, 4, 2, 3}, K = 34
Output: -1

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

• Инициализируйте вектор пары B[] для отслеживания индексов.
• Инициализируйте переменную A с помощью K для хранения значения набора A .
• Пройдите массив arr[] с помощью переменной i ,
  • Добавьте значение arr[i] к A , если индекс не был выбран.
  • Вставьте {brr[i] + 2 * arr[i], i} как пару в вектор B .
• Отсортируйте вектор B в порядке убывания.
• Инициализировать вектор и сохранить выбранные индексы.
• Запустите цикл while и продолжайте выбирать индексы, пока значение A не станет больше, чем B .
• Если все индексы выбраны, но значение B все еще меньше, чем A , выведите «-1» .
• В противном случае выведите размер вектора как минимальное количество ходов.
• Пройдите вектор, an и напечатайте выбранные индексы.

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

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