Elementos máximos que se pueden cruzar usando unidades dadas de a y b

Dada una array binaria de N elementos y dos valores iniciales a y b. Podemos cruzar el i-ésimo elemento si: 
 

1. Si a[i] == 0 , entonces podemos usar 1 unidad de b o a para cruzar el i-ésimo elemento.
2. Si a[i] == 1 , entonces si usamos 1 unidad de b, a aumenta en 1 unidad. En el caso de que se use 1 unidad de a, entonces no hay aumento ni en a ni en b.

La tarea es encontrar el número máximo de elementos que se pueden cruzar usando las unidades a y b. 
Nota : Cuando aumentamos a en 1 en cualquier paso, no puede exceder el valor original de a. 
Ejemplos: 
 

Entrada: arr[] = {0, 1, 0, 1, 0}, a = 1, b = 2; 
Salida: 5 
Use 1 unidad de a para cruzar el 1er elemento. (a = 0 y b = 2) 
Usa 1 unidad de b para cruzar el segundo elemento. (a = 1 y b = 1) 
Usa 1 unidad de a para cruzar el 3er elemento. (a = 0 y b = 1) 
Usa 1 unidad de b para cruzar el 4to elemento. (a = 1 y b = 0) 
Usa 1 unidad de a para cruzar el 5to elemento. (a = 0 y b = 0) 
Entrada: a[] = {1, 0, 0, 1, 0, 1}, a = 1, b = 2 
Use 1 unidad de b para cruzar el primer elemento. (a = 1 yb = 1) 
Usa 1 unidad de b para cruzar el segundo elemento. (a = 1 yb = 0) 
Usa 1 unidad de a para cruzar el tercer elemento. (a = 0 y b = 0) 
Salida: 3 

Enfoque : Iterar en el elemento de array y realizar los siguientes pasos: 
 

• Rompe si no tenemos ni b ni a para pasar el elemento.
• De lo contrario, use b si no queda a, y aumente a en 1 si arr[i] == 1.
• De lo contrario, use a si no queda b.
• De lo contrario, use b si arr[i]==1 y aumente a en 1 hasta el máximo de la a original.
• De lo contrario, simplemente use 1 unidad de a.

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

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number
// of elements crossed
int findElementsCrossed(int arr[], int a, int b, int n)
{
    // Keep a copy of a
    int aa = a;
    int ans = 0;
 
    // Iterate in the binary array
    for (int i = 0; i < n; i++) {
 
        // If no a and b left to use
        if (a == 0 && b == 0)
            break;
 
        // If there is no a
        else if (a == 0) {
 
            // use b and increase a by 1
            // if arr[i] is 1
            if (arr[i] == 1) {
                b -= 1;
                a = min(aa, a + 1);
            }
 
            // simply use b
            else
                b -= 1;
        }
 
        // Use a if theres no b
        else if (b == 0)
            a--;
 
        // Increase a and use b if arr[i] == 1
        else if (arr[i] == 1 && a < aa) {
            b -= 1;
            a = min(aa, a + 1);
        }
 
        // Use a
        else
            a--;
        ans++;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 0, 0, 1, 0, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int a = 1;
    int b = 2;
    cout << findElementsCrossed(arr, a, b, n);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG
{
 
// Function to find the number
// of elements crossed
static int findElementsCrossed(int arr[],
                        int a, int b, int n)
{
    // Keep a copy of a
    int aa = a;
    int ans = 0;
 
    // Iterate in the binary array
    for (int i = 0; i < n; i++)
    {
 
        // If no a and b left to use
        if (a == 0 && b == 0)
            break;
 
        // If there is no a
        else if (a == 0)
        {
 
            // use b and increase a by 1
            // if arr[i] is 1
            if (arr[i] == 1)
            {
                b -= 1;
                a = Math.min(aa, a + 1);
            }
 
            // simply use b
            else
                b -= 1;
        }
 
        // Use a if theres no b
        else if (b == 0)
            a--;
 
        // Increase a and use b if arr[i] == 1
        else if (arr[i] == 1 && a < aa)
        {
            b -= 1;
            a = Math.min(aa, a + 1);
        }
 
        // Use a
        else
            a--;
        ans++;
    }
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 0, 0, 1, 0, 1 };
    int n = arr.length;
    int a = 1;
    int b = 2;
    System.out.println(findElementsCrossed(arr, a, b, n));
 
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 program to implement
# the above approach
 
# Function to find the number
# of elements crossed
def findElementsCrossed(arr, a, b, n):
 
    # Keep a copy of a
    aa = a
    ans = 0
 
    # Iterate in the binary array
    for i in range(n):
 
        # If no a and b left to use
        if (a == 0 and b == 0):
            break
 
        # If there is no a
        elif (a == 0):
 
            # use b and increase a by 1
            # if arr[i] is 1
            if (arr[i] == 1):
                b -= 1
                a = min(aa, a + 1)
             
            # simply use b
            else:
                b -= 1
         
        # Use a if theres no b
        elif (b == 0):
            a -= 1
 
        # Increase a and use b if arr[i] == 1
        elif (arr[i] == 1 and a < aa):
            b -= 1
            a = min(aa, a + 1)
         
        # Use a
        else:
            a -= 1
        ans += 1
     
    return ans
 
# Driver code
arr = [1, 0, 0, 1, 0, 1]
n = len(arr)
a = 1
b = 2
print(findElementsCrossed(arr, a, b, n))
 
# This code is contributed by mohit kumar

// C# implementation of the above approach
using System;
 
class GFG
{
 
// Function to find the number
// of elements crossed
static int findElementsCrossed(int []arr,
                        int a, int b, int n)
{
    // Keep a copy of a
    int aa = a;
    int ans = 0;
 
    // Iterate in the binary array
    for (int i = 0; i < n; i++)
    {
 
        // If no a and b left to use
        if (a == 0 && b == 0)
            break;
 
        // If there is no a
        else if (a == 0)
        {
 
            // use b and increase a by 1
            // if arr[i] is 1
            if (arr[i] == 1)
            {
                b -= 1;
                a = Math.Min(aa, a + 1);
            }
 
            // simply use b
            else
                b -= 1;
        }
 
        // Use a if theres no b
        else if (b == 0)
            a--;
 
        // Increase a and use b if arr[i] == 1
        else if (arr[i] == 1 && a < aa)
        {
            b -= 1;
            a = Math.Min(aa, a + 1);
        }
 
        // Use a
        else
            a--;
        ans++;
    }
 
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 1, 0, 0, 1, 0, 1 };
    int n = arr.Length;
    int a = 1;
    int b = 2;
    Console.WriteLine(findElementsCrossed(arr, a, b, n));
 
}
}
 
// This code contributed by Rajput-Ji

<?php
// PHP program to implement
// the above approach
 
// Function to find the number
// of elements crossed
function findElementsCrossed($arr, $a, $b, $n)
{
    // Keep a copy of a
    $aa = $a;
    $ans = 0;
 
    // Iterate in the binary array
    for ($i = 0; $i < $n; $i++)
    {
 
        // If no a and b left to use
        if ($a == 0 && $b == 0)
            break;
 
        // If there is no a
        else if ($a == 0)
        {
 
            // use b and increase a by 1
            // if arr[i] is 1
            if ($arr[$i] == 1)
            {
                $b -= 1;
                $a = min($aa, $a + 1);
            }
 
            // simply use b
            else
                $b -= 1;
        }
 
        // Use a if theres no b
        else if ($b == 0)
            $a--;
 
        // Increase a and use b if arr[i] == 1
        else if ($arr[$i] == 1 && $a < $aa)
        {
            $b -= 1;
            $a = min($aa, $a + 1);
        }
 
        // Use a
        else
            $a--;
        $ans++;
    }
 
    return $ans;
}
 
// Driver code
$arr = array(1, 0, 0, 1, 0, 1);
$n = sizeof($arr);
$a = 1;
$b = 2;
echo findElementsCrossed($arr, $a, $b, $n);
 
// This code is contributed by Akanksha Rai
?>

<script>
// javascript program to implement
// the above approach
 
    // Function to find the number
    // of elements crossed
    function findElementsCrossed(arr , a , b , n) {
        // Keep a copy of a
        var aa = a;
        var ans = 0;
 
        // Iterate in the binary array
        for (i = 0; i < n; i++) {
 
            // If no a and b left to use
            if (a == 0 && b == 0)
                break;
 
            // If there is no a
            else if (a == 0) {
 
                // use b and increase a by 1
                // if arr[i] is 1
                if (arr[i] == 1) {
                    b -= 1;
                    a = Math.min(aa, a + 1);
                }
 
                // simply use b
                else
                    b -= 1;
            }
 
            // Use a if theres no b
            else if (b == 0)
                a--;
 
            // Increase a and use b if arr[i] == 1
            else if (arr[i] == 1 && a < aa) {
                b -= 1;
                a = Math.min(aa, a + 1);
            }
 
            // Use a
            else
                a--;
            ans++;
        }
 
        return ans;
    }
 
    // Driver code
     
        var arr = [ 1, 0, 0, 1, 0, 1 ];
        var n = arr.length;
        var a = 1;
        var b = 2;
        document.write(findElementsCrossed(arr, a, b, n));
 
 
// This code contributed by umadevi9616
</script>

3

Complejidad de tiempo: O(n), para iterar sobre el arreglo donde n es el tamaño del arreglo
Espacio auxiliar: O(1)