Dado un entero K y dos arreglos A[] y B[] que consisten en N y M enteros, la tarea es maximizar la cantidad de elementos que se pueden eliminar del frente de cualquiera de los arreglos de acuerdo con las siguientes reglas:
- Elimina un elemento del frente de cualquiera de los arreglos A[] y B[] de modo que el valor del elemento eliminado debe ser como máximo K .
- Disminuya el valor de K por el valor del elemento eliminado.
Ejemplos:
Entrada: K = 7, A[] = {2, 4, 7, 3}, B[] = {1, 9, 3, 4, 5}
Salida: 3
Explicación:
Operación 1: Elija el elemento de la array A[ ] y disminuya K en A[0](=2), entonces el valor de K se convierte en = (7 – 2) = 5.
Operación 2: elija el elemento de la array B[] y disminuya K en B[0](=1 ), luego el valor de K se convierte en = (5 – 1) = 4.
Operación 3: Elija el elemento de la array A[] y disminuya K en A[1](=4), luego el valor de K se convierte en = (4 – 4 ) = 4.
Después de las operaciones anteriores, no se pueden eliminar más elementos. Por lo tanto, imprime 3.Entrada: K = 9, A[] = {12, 10, 1, 2, 3}, B[] = {15, 19, 3, 4, 5}
Salida: 0
Enfoque: El problema dado se puede resolver utilizando la suma de prefijos y la búsqueda binaria para encontrar el total de elementos j que se pueden tomar de la pila B después de tomar i elementos de la pila A y devolver el resultado como el valor máximo de (i + j) . Siga los pasos a continuación para resolver el problema dado:
- Encuentre la suma de prefijos de las arrays A[] y B[] .
- Inicialice una variable, digamos contar como 0 , que almacene el máximo de elementos que se pueden tomar.
- Recorra la array , A[] sobre el rango [0, N] usando la variable i y realice los siguientes pasos:
- Si el valor de A[i] es mayor que K , salga del bucle .
- Almacene la cantidad restante después de tomar i elementos de la pila A en una variable, rem como K – A[i] .
- Realice una búsqueda binaria en la array B para encontrar el máximo de elementos, por ejemplo, j que se pueden tomar en cantidad rem de la pila B (después de tomar i elementos de la pila A ).
- Almacene el valor máximo de i + j en la variable cuenta .
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number
// of items that can be removed from
// both the arrays
void maxItems(int n, int m, int a[],
int b[], int K)
{
// Stores the maximum item count
int count = 0;
// Stores the prefix sum of the
// cost of items
int A[n + 1];
int B[m + 1];
// Insert the item cost 0 at the
// front of the arrays
A[0] = 0;
B[0] = 0;
// Build the prefix sum for
// the array A[]
for (int i = 1; i <= n; i++) {
// Update the value of A[i]
A[i] = a[i - 1] + A[i - 1];
}
// Build the prefix sum for
// the array B[]
for (int i = 1; i <= m; i++) {
// Update the value of B[i]
B[i] = b[i - 1] + B[i - 1];
}
// Iterate through each item
// of the array A[]
for (int i = 0; i <= n; i++) {
// If A[i] exceeds K
if (A[i] > K)
break;
// Store the remaining amount
// after taking top i elements
// from the array A
int rem = K - A[i];
// Store the number of items
// possible to take from the
// array B[]
int j = 0;
// Store low and high bounds
// for binary search
int lo = 0, hi = m;
// Binary search to find
// number of item that
// can be taken from stack
// B in rem amount
while (lo <= hi) {
// Calculate the mid value
int mid = (lo + hi) / 2;
if (B[mid] <= rem) {
// Update the value
// of j and lo
j = mid;
lo = mid + 1;
}
else {
// Update the value
// of the hi
hi = mid - 1;
}
}
// Store the maximum of total
// item count
count = max(j + i, count);
}
// Print the result
cout << count;
}
// Driver Code
int main()
{
int n = 4, m = 5, K = 7;
int A[n] = { 2, 4, 7, 3 };
int B[m] = { 1, 9, 3, 4, 5 };
maxItems(n, m, A, B, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the maximum number
// of items that can be removed from
// both the arrays
static void maxItems(int n, int m, int a[],
int b[], int K)
{
// Stores the maximum item count
int count = 0;
// Stores the prefix sum of the
// cost of items
int A[] = new int[n + 1];
int B[] = new int[m + 1];
// Insert the item cost 0 at the
// front of the arrays
A[0] = 0;
B[0] = 0;
// Build the prefix sum for
// the array A[]
for(int i = 1; i <= n; i++)
{
// Update the value of A[i]
A[i] = a[i - 1] + A[i - 1];
}
// Build the prefix sum for
// the array B[]
for(int i = 1; i <= m; i++)
{
// Update the value of B[i]
B[i] = b[i - 1] + B[i - 1];
}
// Iterate through each item
// of the array A[]
for(int i = 0; i <= n; i++)
{
// If A[i] exceeds K
if (A[i] > K)
break;
// Store the remaining amount
// after taking top i elements
// from the array A
int rem = K - A[i];
// Store the number of items
// possible to take from the
// array B[]
int j = 0;
// Store low and high bounds
// for binary search
int lo = 0, hi = m;
// Binary search to find
// number of item that
// can be taken from stack
// B in rem amount
while (lo <= hi)
{
// Calculate the mid value
int mid = (lo + hi) / 2;
if (B[mid] <= rem)
{
// Update the value
// of j and lo
j = mid;
lo = mid + 1;
}
else
{
// Update the value
// of the hi
hi = mid - 1;
}
}
// Store the maximum of total
// item count
count = Math.max(j + i, count);
}
// Print the result
System.out.print(count);
}
// Driver Code
public static void main (String[] args)
{
int n = 4, m = 5, K = 7;
int A[] = { 2, 4, 7, 3 };
int B[] = { 1, 9, 3, 4, 5 };
maxItems(n, m, A, B, K);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find the maximum number # of items that can be removed from # both the arrays def maxItems(n, m, a, b, K): # Stores the maximum item count count = 0 # Stores the prefix sum of the # cost of items A = [0 for i in range(n + 1)] B = [0 for i in range(m + 1)] # Build the prefix sum for # the array A[] for i in range(1, n + 1, 1): # Update the value of A[i] A[i] = a[i - 1] + A[i - 1] # Build the prefix sum for # the array B[] for i in range(1, m + 1, 1): # Update the value of B[i] B[i] = b[i - 1] + B[i - 1] # Iterate through each item # of the array A[] for i in range(n + 1): # If A[i] exceeds K if (A[i] > K): break # Store the remaining amount # after taking top i elements # from the array A rem = K - A[i] # Store the number of items # possible to take from the # array B[] j = 0 # Store low and high bounds # for binary search lo = 0 hi = m # Binary search to find # number of item that # can be taken from stack # B in rem amount while (lo <= hi): # Calculate the mid value mid = (lo + hi) // 2 if (B[mid] <= rem): # Update the value # of j and lo j = mid lo = mid + 1 else: # Update the value # of the hi hi = mid - 1 # Store the maximum of total # item count count = max(j + i, count) # Print the result print(count) # Driver Code if __name__ == '__main__': n = 4 m = 5 K = 7 A = [ 2, 4, 7, 3 ] B = [ 1, 9, 3, 4, 5 ] maxItems(n, m, A, B, K) # This code is contributed by bgangwar59
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the maximum number
// of items that can be removed from
// both the arrays
static void maxItems(int n, int m, int[] a,
int[] b, int K)
{
// Stores the maximum item count
int count = 0;
// Stores the prefix sum of the
// cost of items
int[] A = new int[n + 1];
int[] B= new int[m + 1];
// Insert the item cost 0 at the
// front of the arrays
A[0] = 0;
B[0] = 0;
// Build the prefix sum for
// the array A[]
for(int i = 1; i <= n; i++)
{
// Update the value of A[i]
A[i] = a[i - 1] + A[i - 1];
}
// Build the prefix sum for
// the array B[]
for(int i = 1; i <= m; i++)
{
// Update the value of B[i]
B[i] = b[i - 1] + B[i - 1];
}
// Iterate through each item
// of the array A[]
for(int i = 0; i <= n; i++)
{
// If A[i] exceeds K
if (A[i] > K)
break;
// Store the remaining amount
// after taking top i elements
// from the array A
int rem = K - A[i];
// Store the number of items
// possible to take from the
// array B[]
int j = 0;
// Store low and high bounds
// for binary search
int lo = 0, hi = m;
// Binary search to find
// number of item that
// can be taken from stack
// B in rem amount
while (lo <= hi)
{
// Calculate the mid value
int mid = (lo + hi) / 2;
if (B[mid] <= rem)
{
// Update the value
// of j and lo
j = mid;
lo = mid + 1;
}
else
{
// Update the value
// of the hi
hi = mid - 1;
}
}
// Store the maximum of total
// item count
count = Math.Max(j + i, count);
}
// Print the result
Console.Write(count);
}
// Driver code
public static void Main(String []args)
{
int n = 4, m = 5, K = 7;
int[] A = { 2, 4, 7, 3 };
int[] B = { 1, 9, 3, 4, 5 };
maxItems(n, m, A, B, K);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// javascript program for the above approach
// Function to find the maximum number
// of items that can be removed from
// both the arrays
function maxItems(n, m, a, b, K)
{
// Stores the maximum item count
var count = 0;
// Stores the prefix sum of the
// cost of items
var A = new Array(n + 1);
var B = new Array(m + 1);
// Insert the item cost 0 at the
// front of the arrays
A[0] = 0;
B[0] = 0;
var i;
// Build the prefix sum for
// the array A[]
for (i = 1; i <= n; i++) {
// Update the value of A[i]
A[i] = a[i - 1] + A[i - 1];
}
// Build the prefix sum for
// the array B[]
for (i = 1; i <= m; i++) {
// Update the value of B[i]
B[i] = b[i - 1] + B[i - 1];
}
// Iterate through each item
// of the array A[]
for (i = 0; i <= n; i++) {
// If A[i] exceeds K
if (A[i] > K)
break;
// Store the remaining amount
// after taking top i elements
// from the array A
var rem = K - A[i];
// Store the number of items
// possible to take from the
// array B[]
var j = 0;
// Store low and high bounds
// for binary search
var lo = 0, hi = m;
// Binary search to find
// number of item that
// can be taken from stack
// B in rem amount
while (lo <= hi) {
// Calculate the mid value
var mid = parseInt((lo + hi) / 2);
if (B[mid] <= rem) {
// Update the value
// of j and lo
j = mid;
lo = mid + 1;
}
else {
// Update the value
// of the hi
hi = mid - 1;
}
}
// Store the maximum of total
// item count
count = Math.max(j + i, count);
}
// Print the result
document.write(count);
}
// Driver Code
var n = 4, m = 5, K = 7;
var A = [2, 4, 7, 3];
var B = [1, 9, 3, 4, 5];
maxItems(n, m, A, B, K);
// This code is contributed by SURENDRA_GANGWAR.
</script>
Producción:
3
Complejidad de tiempo: O(N * log(M))
Espacio auxiliar: O(N + M)
Publicación traducida automáticamente
Artículo escrito por UtkarshPandey6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA