Maximice las cajas requeridas para mantener al menos una camisa negra y una blanca

Dados tres números W , B y O que representan las cantidades de camisas blancas, negras y de otros colores respectivamente, la tarea es encontrar el número máximo de cajas requeridas para que cada caja contenga tres camisas que consisten en al menos una camisa blanca y otra negra usando la cantidad dada de camisas.

Ejemplos:

Entrada: W = 3, B = 3, O = 1
Salida: 2
Explicación:
A continuación se muestra la distribución de camisetas en las casillas:
Casilla 1: 1 camiseta blanca, 1 camiseta negra y 1 camiseta de otro color.
Caja 2: 2 camisetas blancas y 1 camiseta negra.
Caja 3: 1 camisa negra
Dado que solo 2 cajas cumplen la condición dada, que es el número máximo posible de cajas con la cantidad dada de camisas. Por lo tanto, imprime 2.

Entrada: W = 4, B = 6, O = 0
Salida: 3

Enfoque: el problema dado se puede resolver utilizando la búsqueda binaria . La idea es buscar el máximo número de casillas en el espacio de búsqueda formado por el límite inferior y superior . Se puede observar que el límite inferior y el límite superior del conteo de la caja es 0 y mínimo de W y B respectivamente. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans como 0 para almacenar el resultado requerido.
• Inicialice dos variables, digamos bajo como 0 y alto como el mínimo de (W, B) .
• Repita hasta que el valor de bajo sea menor que alto y realice los siguientes pasos:
  • Encuentre el valor medio de low y high en una variable, digamos mid .
  • Compruebe si el número máximo de casillas puede ser igual a mid , luego actualice el valor de ans a mid y actualice el espacio de búsqueda en la mitad derecha actualizando el valor de low .
  • De lo contrario, actualice el espacio de búsqueda a la mitad izquierda actualizando el valor de alto .
• Imprime el valor de ans como resultado.

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 find the maximum number
// of boxes such that each box contains
// three shirts comprising of at least
// one white and black shirt
void numberofBoxes(int W, int B, int O)
{
    // Stores the low and high pointers
    // for binary search
    int low = 0, high = min(W, B);
 
    // Store the required answer
    int ans = 0;
 
    // Loop while low <= high
    while (low <= high) {
 
        // Store the mid value
        int mid = low + (high - low) / 2;
 
        // Check if the mid number of
        // boxes can be used
        if (((W >= mid) and (B >= mid))
            and ((W - mid) + (B - mid) + O)
                    >= mid) {
 
            // Update answer and recur
            // for the right half
            ans = mid;
            low = mid + 1;
        }
 
        // Else, recur for the left half
        else
            high = mid - 1;
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    int W = 3, B = 3, O = 1;
    numberofBoxes(W, B, O);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the maximum number
// of boxes such that each box contains
// three shirts comprising of at least
// one white and black shirt
static void numberofBoxes(int W, int B, int O)
{
     
    // Stores the low and high pointers
    // for binary search
    int low = 0, high = Math.min(W, B);
 
    // Store the required answer
    int ans = 0;
 
    // Loop while low <= high
    while (low <= high)
    {
         
        // Store the mid value
        int mid = low + (high - low) / 2;
 
        // Check if the mid number of
        // boxes can be used
        if (((W >= mid) && (B >= mid)) &&
            ((W - mid) + (B - mid) + O) >= mid)
        {
             
            // Update answer and recur
            // for the right half
            ans = mid;
            low = mid + 1;
        }
 
        // Else, recur for the left half
        else
            high = mid - 1;
    }
 
    // Print the result
    System.out.println(ans);
}
 
// Driver Code
public static void main(String args[])
{
    int W = 3, B = 3, O = 1;
     
    numberofBoxes(W, B, O);
}
}
 
// This code is contributed by avijitmondal1998

# Python3 program for the above approach
 
# Function to find the maximum number
# of boxes such that each box contains
# three shirts comprising of at least
# one white and black shirt
def numberofBoxes(W, B, O):
   
    # Stores the low and high pointers
    # for binary search
    low = 0
    high = min(W, B)
 
    # Store the required answer
    ans = 0
 
    # Loop while low <= high
    while (low <= high):
 
        # Store the mid value
        mid = low + (high - low) // 2
 
        # Check if the mid number of
        # boxes can be used
        if (((W >= mid) and (B >= mid)) and ((W - mid) + (B - mid) + O) >= mid):
            # Update answer and recur
            # for the right half
            ans = mid
            low = mid + 1
 
        # Else, recur for the left half
        else:
            high = mid - 1
 
    # Print result
    print (ans)
 
# Driver Code
if __name__ == '__main__':
    W = 3
    B = 3
    O = 1
    numberofBoxes(W, B, O)
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
 
using System;
class GFG {
 
    // Function to find the maximum number
    // of boxes such that each box contains
    // three shirts comprising of at least
    // one white and black shirt
    static void numberofBoxes(int W, int B, int O)
    {
        // Stores the low and high pointers
        // for binary search
        int low = 0, high = Math.Min(W, B);
 
        // Store the required answer
        int ans = 0;
 
        // Loop while low <= high
        while (low <= high) {
 
            // Store the mid value
            int mid = low + (high - low) / 2;
 
            // Check if the mid number of
            // boxes can be used
            if (((W >= mid) &&(B >= mid))
                    &&((W - mid) + (B - mid) + O)
                >= mid) {
 
                // Update answer and recur
                // for the right half
                ans = mid;
                low = mid + 1;
            }
 
            // Else, recur for the left half
            else
                high = mid - 1;
        }
 
        // Print the result
        Console.Write(ans);
    }
 
    // Driver Code
    public static void Main()
    {
        int W = 3, B = 3, O = 1;
        numberofBoxes(W, B, O);
    }
}
 
// This code is contributed by ukasp.

<script>
 
// Javascript program for the above approach
 
// Function to find the maximum number
// of boxes such that each box contains
// three shirts comprising of at least
// one white and black shirt
function numberofBoxes(W, B, O)
{
     
    // Stores the low and high pointers
    // for binary search
    let low = 0, high = Math.min(W, B);
 
    // Store the required answer
    let ans = 0;
 
    // Loop while low <= high
    while (low <= high)
    {
         
        // Store the mid value
        let mid = low + Math.floor((high - low) / 2);
 
        // Check if the mid number of
        // boxes can be used
        if (((W >= mid) && (B >= mid)) &&
            ((W - mid) + (B - mid) + O) >= mid)
        {
             
            // Update answer and recur
            // for the right half
            ans = mid;
            low = mid + 1;
        }
 
        // Else, recur for the left half
        else
            high = mid - 1;
    }
 
    // Print the result
    document.write(ans);
}
 
// Driver Code
let W = 3, B = 3, O = 1;
numberofBoxes(W, B, O);
 
// This code is contributed by gfgking
 
</script>

2

Complejidad de tiempo: O(log(min(W, B)))
Espacio auxiliar: O(1)