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

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

Примеры:

Input: arr[] = {2, 3}, cap[] = {5, 6}
Output: 5
Explanation:
Following operations are performed to maximize value of any element in arr[]:
Operation 1: Decrease arr[0] by 2 and increase arr[1] by 2. Now arr[] = {0, 5}.
Therefore, the maximum element in arr[] is 5.

Input: arr[] = {1, 2, 1}, cap[] = {2, 3, 2}
Output: 3

Подход: Данная проблема может быть решена с помощью Жадного подхода, основанного на наблюдении, что после выполнения любого количества операций максимальное значение не может превышать максимальную емкость в cap[]. Поэтому ответ будет min( сумма всех элементов массива, максимальная емкость в шапке[]) .

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

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