Maximice el primer elemento de la array realizando operaciones dadas como máximo K veces

Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar el primer elemento de la array para maximizar realizando las siguientes operaciones como máximo K veces: 

1. Elija un par de índices i y j (0 ≤ i, j ≤ N-1) tales que |i − j| = 1 y arr _i > 0 .
2. Establezca arr _i = arr _i − 1 y arr _j = arr _j + 1 en esos dos índices.

Ejemplos:

Entrada: arr[ ] = {1, 0, 3, 2}, K = 5
Salida: 3
Explicación:
Uno de los posibles conjuntos de operaciones puede ser:
Operación 1: Seleccionar i = 3 y j = 2 . Por lo tanto, la array se modifica a {1, 1, 2, 2}.
Operación 2: Seleccione i = 3 y j = 2 . Por lo tanto, la array se modifica a {1, 2, 1, 2}.
Operación 3: Seleccione i = 2 y j = 1 . Por lo tanto, la array se modifica a {2, 1, 1, 2}.
Operación 4: Seleccionar i = 2 y j = 1 . Por lo tanto, la array se modifica a {3, 0, 1, 2}.

Entrada: arr[] = {5, 1}, K = 2
Salida: 6

Enfoque: siga los pasos a continuación para resolver el problema:

1. En cualquier punto, es óptimo elegir los índices i y j más cercanos al primer elemento de la array, con i > j .
2. Por lo tanto, para cada operación, recorra la array de izquierda a derecha y mueva los elementos más cerca del primer elemento.
3. Si todos los elementos están en la primera posición en algún punto, deje de recorrer e imprima el primer elemento de la array.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximize
// the first array element
int getMax(int arr[], int N, int K)
{
 
    // Traverse the array
    for (int i = 1; i < N; i++) {
 
        // Initialize cur_val to a[i]
        int cur_val = arr[i];
 
        // If all operations
        // are not over yet
        while (K >= i) {
 
            // If current value is
            // greater than zero
            if (cur_val > 0) {
 
                // Incrementing first
                // element of array by 1
                arr[0] = arr[0] + 1;
 
                // Decrementing current
                // value of array by 1
                cur_val = cur_val - 1;
 
                // Decrementing number
                // of operations by i
                K = K - i;
            }
 
            // If current value is
            // zero, then break
            else
                break;
        }
    }
 
    // Print first array element
    cout << arr[0];
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 1, 0, 3, 2 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given K
    int K = 5;
 
    // Prints the maximum
    // possible value of the
    // first array element
    getMax(arr, N, K);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
  // Function to maximize
  // the first array element
  static void getMax(int arr[], int N, int K)
  {
 
    // Traverse the array
    for (int i = 1; i < N; i++)
    {
 
      // Initialize cur_val to a[i]
      int cur_val = arr[i];
 
      // If all operations
      // are not over yet
      while (K >= i)
      {
 
        // If current value is
        // greater than zero
        if (cur_val > 0)
        {
 
          // Incrementing first
          // element of array by 1
          arr[0] = arr[0] + 1;
 
          // Decrementing current
          // value of array by 1
          cur_val = cur_val - 1;
 
          // Decrementing number
          // of operations by i
          K = K - i;
        }
 
        // If current value is
        // zero, then break
        else
          break;
      }
    }
 
    // Print first array element
    System.out.print(arr[0]);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
     
    // Given array
    int arr[] = { 1, 0, 3, 2 };
 
    // Size of the array
    int N = arr.length;
 
    // Given K
    int K = 5;
 
    // Prints the maximum
    // possible value of the
    // first array element
    getMax(arr, N, K);
  }
}
 
// This code is contributed by shikhasingrajput

# Python3 program for the above approach
 
# Function to maximize
# the first array element
def getMax(arr, N, K):
     
    # Traverse the array
    for i in range(1, N, 1):
         
        # Initialize cur_val to a[i]
        cur_val = arr[i]
 
        # If all operations
        # are not over yet
        while (K >= i):
             
            # If current value is
            # greater than zero
            if (cur_val > 0):
 
                # Incrementing first
                # element of array by 1
                arr[0] = arr[0] + 1
 
                # Decrementing current
                # value of array by 1
                cur_val = cur_val - 1
 
                # Decrementing number
                # of operations by i
                K = K - i
 
            # If current value is
            # zero, then break
            else:
                break
 
    # Print first array element
    print(arr[0])
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [ 1, 0, 3, 2 ]
 
    # Size of the array
    N = len(arr)
 
    # Given K
    K = 5
 
    # Prints the maximum
    # possible value of the
    # first array element
    getMax(arr, N, K)
 
# This code is contributed by SURENDRA_GANGWAR

// C# program for the above approach
using System;
 
class GFG{
     
// Function to maximize
// the first array element
static void getMax(int[] arr, int N,
                   int K)
{
     
    // Traverse the array
    for(int i = 1; i < N; i++)
    {
         
        // Initialize cur_val to a[i]
        int cur_val = arr[i];
   
        // If all operations
        // are not over yet
        while (K >= i)
        {
             
            // If current value is
            // greater than zero
            if (cur_val > 0)
            {
                 
                // Incrementing first
                // element of array by 1
                arr[0] = arr[0] + 1;
                 
                // Decrementing current
                // value of array by 1
                cur_val = cur_val - 1;
                 
                // Decrementing number
                // of operations by i
                K = K - i;
            }
   
            // If current value is
            // zero, then break
            else
                break;
        }
    }
     
    // Print first array element
    Console.Write(arr[0]);
} 
 
// Driver code
static void Main()
{
     
    // Given array
    int[] arr = { 1, 0, 3, 2 };
     
    // Size of the array
    int N = arr.Length;
     
    // Given K
    int K = 5;
     
    // Prints the maximum
    // possible value of the
    // first array element
    getMax(arr, N, K);
}
}
 
// This code is contributed by divyesh072019

<script>
// javascript program for the above approach   
// Function to maximize
    // the first array element
    function getMax(arr , N , K) {
 
        // Traverse the array
        for (i = 1; i < N; i++) {
 
            // Initialize cur_val to a[i]
            var cur_val = arr[i];
 
            // If all operations
            // are not over yet
            while (K >= i) {
 
                // If current value is
                // greater than zero
                if (cur_val > 0) {
 
                    // Incrementing first
                    // element of array by 1
                    arr[0] = arr[0] + 1;
 
                    // Decrementing current
                    // value of array by 1
                    cur_val = cur_val - 1;
 
                    // Decrementing number
                    // of operations by i
                    K = K - i;
                }
 
                // If current value is
                // zero, then break
                else
                    break;
            }
        }
 
        // Print first array element
        document.write(arr[0]);
    }
 
    // Driver Code
     
        // Given array
        var arr = [ 1, 0, 3, 2 ];
 
        // Size of the array
        var N = arr.length;
 
        // Given K
        var K = 5;
 
        // Prints the maximum
        // possible value of the
        // first array element
        getMax(arr, N, K);
 
// This code is contributed by aashish1995
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)