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

Для заданных двух массивов A[] и B[] , состоящих из N положительных целых чисел, задача состоит в том, чтобы найти минимальный размер подмножеств пары элементов (A[i], B[i]) , такой, что сумма всех пар подмножеств — это по крайней мере сумма оставшихся элементов массива A[] , которые не входят в подмножество, т. е . (A[0] + B[0] + A[1] + B[1] + … + A[K – 1] + B[K – 1] >= A[K + 1] + … + A[N – 1] .

Примеры:

Input: A[] = {3, 2, 2}, B[] = {2, 3, 1}
Output: 1
Explanation:
Choose the subset as {(3, 2)}. Now, the sum of subsets is 3 + 2 = 5, which greater than sum of remaining A[] = 3 + 1 = 4.

Input: A[] = {2, 2, 2, 2, 2}, B[] = {1, 1, 1, 1, 1}  
Output: 3

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

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

Эффективный подход: данная проблема может быть решена с использованием жадного подхода, идея состоит в том, чтобы использовать сортировку, и можно сделать наблюдение, что при выборе i ^-й пары как части результирующего подмножества разница между двумя подмножествами уменьшается на величину ( 2*S[i] + U[i]) . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте массив, скажем, разность[] размера N , в котором хранится значение (2*A[i] + B[i]) для каждой пары элементов.
• Инициализируйте переменную, скажем, sum , которая отслеживает сумму оставшихся элементов массива A[i] .
• Инициализируйте переменную, скажем, K , которая отслеживает размер результирующего подмножества.
• Переберите диапазон [0, N) и обновите значение разности[i] как значение (2*A[i] + B[i]) и уменьшите значение суммы на значение A[i] .
• Отсортируйте заданный массив разность[] в порядке возрастания.
• Пройдите массив разность[] в обратном порядке, пока сумма не станет отрицательной, добавьте значение разности[i] к сумме и увеличьте значение К на 1 .
• После выполнения вышеуказанных шагов выведите в качестве результата значение K.

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

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