Dadas dos pilas stack1[] y stack2[] de tamaño N y M respectivamente y un entero K , la tarea es contar el número máximo de enteros de dos pilas que tienen una suma menor o igual que K .
Ejemplos:
Entrada: pila1[ ] = { 60, 90, 120 }
pila2[ ] = { 100, 10, 10, 250 }, K = 130
Salida: 3
Explicación: Tome 3 números de la pila1 que son 100 y 10 y 10.
Suma total 100 + 10 + 10 = 120Entrada: pila1[ ] = { 60, 90, 120 }
pila2[ ] = { 80, 150, 80, 150 }, K = 740
Salida: 7
Explicación: Seleccione todos los números porque el valor K es suficiente.
Enfoque: este problema no se puede resolver utilizando el enfoque Greedy porque en Greedy en cada paso se seleccionará el número que tenga el valor mínimo, pero el primer ejemplo falla de acuerdo con esto. Este problema se puede resolver utilizando la suma de prefijos y la búsqueda binaria . calcule la suma del prefijo de ambas pilas y ahora itere para cada valor posible de la primera pila y tome el objetivo que es (K – stack1[i]) y aplique la búsqueda binaria en la segunda pila para tomar el límite inferior de stack2[] .
Siga los pasos que se mencionan a continuación:
- Tome dos nuevas pilas que son sumA[] y sumB[] .
- Calcula el prefijo de las pilas stack1[] y stack2[] .
- Iterar en la primera pila.
- Ahora, tome la variable remValueOfK y almacene (K – stack1[i]) .
- Si es menor que 0, continúa el bucle.
- De lo contrario, tome el límite inferior de la segunda pila.
- Si el límite inferior es mayor que el tamaño de la segunda pila o el valor del límite inferior es mayor que el valor de remValueOfK simplemente disminuya el valor de la variable del límite inferior.
- Almacene el recuento máximo de elementos seleccionados y devuélvalo como la respuesta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// maximum number of elements
int maxNumbers(int stack1[], int N, int stack2[],
int M, int K)
{
// Take prefix of both the stack
vector<int> sumA(N + 1, 0);
vector<int> sumB(M + 1, 0);
for (int i = 0; i < N; i++)
sumA[i + 1] = sumA[i] + stack1[i];
for (int i = 0; i < M; i++)
sumB[i + 1] = sumB[i] + stack2[i];
// Calculate maxNumbers
int MaxNumbers = 0;
for (int i = 0; i <= N; i++) {
// Calculate remaining value of K
// after selecting numbers
// from 1st stack
int remValueOfK = K - sumA[i];
// If rem value of K is less than 0
// continue the loop
if (remValueOfK < 0)
continue;
// Calculate lower bound
int lowerBound
= lower_bound(sumB.begin(),
sumB.end(),
remValueOfK)
- sumB.begin();
// If size of lower bound is greater
// than self stack size or
// value of lower bound element
// decrement lowerBound
if (lowerBound > M
or sumB[lowerBound] > remValueOfK) {
lowerBound--;
}
// Store max possible numbers
int books = i + lowerBound;
MaxNumbers = max(MaxNumbers, books);
}
return MaxNumbers;
}
// Driver code
int main()
{
int stack1[] = { 60, 90, 120 };
int stack2[] = { 100, 10, 10, 200 };
int K = 130;
int N = 3;
int M = 4;
int ans
= maxNumbers(stack1, N, stack2, M, K);
cout << ans;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
static int lower_bound(int []a, int val) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int mid = (int)Math.floor(lo + (double)(hi - lo) / 2);
if (a[mid] < val)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
// Function to find the
// maximum number of elements
static int maxNumbers(int []stack1, int N, int []stack2,
int M, int K) {
// Take prefix of both the stack
int []sumA = new int[N + 1];
for(int i = 0; i < N + 1; i++) {
sumA[i] = 0;
}
int []sumB = new int[M + 1];
for(int i = 0; i < M + 1; i++) {
sumB[i] = 0;
}
for (int i = 0; i < N; i++)
sumA[i + 1] = sumA[i] + stack1[i];
for (int i = 0; i < M; i++)
sumB[i + 1] = sumB[i] + stack2[i];
// Calculate maxNumbers
int MaxNumbers = 0;
for (int i = 0; i <= N; i++) {
// Calculate remaining value of K
// after selecting numbers
// from 1st stack
int remValueOfK = K - sumA[i];
// If rem value of K is less than 0
// continue the loop
if (remValueOfK < 0)
continue;
// Calculate lower bound
int lowerBound
= lower_bound(sumB,
remValueOfK);
// If size of lower bound is greater
// than self stack size or
// value of lower bound element
// decrement lowerBound
if (lowerBound > M
|| sumB[lowerBound] > remValueOfK) {
lowerBound--;
}
// Store max possible numbers
int books = i + lowerBound;
MaxNumbers = Math.max(MaxNumbers, books);
}
return MaxNumbers;
}
// Driver Code
public static void main(String args[])
{
int []stack1 = {60, 90, 120};
int []stack2 = {100, 10, 10, 200};
int K = 130;
int N = 3;
int M = 4;
int ans = maxNumbers(stack1, N, stack2, M, K);
System.out.println(ans);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python code for the above approach def lower_bound(a, val): lo = 0 hi = len(a) - 1; while (lo < hi): mid = (lo + (hi - lo) // 2); if (a[mid] < val): lo = mid + 1; else: hi = mid; return lo; # Function to find the # maximum number of elements def maxNumbers(stack1, N, stack2, M, K): # Take prefix of both the stack sumA = [0] * (N + 1) sumB = [0] * (M + 1) for i in range(N): sumA[i + 1] = sumA[i] + stack1[i]; for i in range(M): sumB[i + 1] = sumB[i] + stack2[i]; # Calculate maxNumbers MaxNumbers = 0; for i in range(N + 1): # Calculate remaining value of K # after selecting numbers # from 1st stack remValueOfK = K - sumA[i]; # If rem value of K is less than 0 # continue the loop if (remValueOfK < 0): continue; # Calculate lower bound lowerBound = lower_bound(sumB, remValueOfK); # If size of lower bound is greater # than self stack size or # value of lower bound element # decrement lowerBound if (lowerBound > M or sumB[lowerBound] > remValueOfK): lowerBound -= 1 # Store max possible numbers books = i + lowerBound; MaxNumbers = max(MaxNumbers, books); return MaxNumbers; # Driver code stack1 = [60, 90, 120]; stack2 = [100, 10, 10, 200]; K = 130; N = 3; M = 4; ans = maxNumbers(stack1, N, stack2, M, K); print(ans) # This code is contributed by gfgking
C#
// C# code for the above approach
using System;
class GFG
{
static int lower_bound(int []a, int val) {
int lo = 0, hi = a.Length - 1;
while (lo < hi) {
int mid = (int)Math.Floor(lo + (double)(hi - lo) / 2);
if (a[mid] < val)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
// Function to find the
// maximum number of elements
static int maxNumbers(int []stack1, int N, int []stack2,
int M, int K) {
// Take prefix of both the stack
int []sumA = new int[N + 1];
for(int i = 0; i < N + 1; i++) {
sumA[i] = 0;
}
int []sumB = new int[M + 1];
for(int i = 0; i < M + 1; i++) {
sumB[i] = 0;
}
for (int i = 0; i < N; i++)
sumA[i + 1] = sumA[i] + stack1[i];
for (int i = 0; i < M; i++)
sumB[i + 1] = sumB[i] + stack2[i];
// Calculate maxNumbers
int MaxNumbers = 0;
for (int i = 0; i <= N; i++) {
// Calculate remaining value of K
// after selecting numbers
// from 1st stack
int remValueOfK = K - sumA[i];
// If rem value of K is less than 0
// continue the loop
if (remValueOfK < 0)
continue;
// Calculate lower bound
int lowerBound
= lower_bound(sumB,
remValueOfK);
// If size of lower bound is greater
// than self stack size or
// value of lower bound element
// decrement lowerBound
if (lowerBound > M
|| sumB[lowerBound] > remValueOfK) {
lowerBound--;
}
// Store max possible numbers
int books = i + lowerBound;
MaxNumbers = Math.Max(MaxNumbers, books);
}
return MaxNumbers;
}
// Driver code
public static void Main() {
int []stack1 = {60, 90, 120};
int []stack2 = {100, 10, 10, 200};
int K = 130;
int N = 3;
int M = 4;
int ans = maxNumbers(stack1, N, stack2, M, K);
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
function lower_bound(a, val) {
let lo = 0, hi = a.length - 1;
while (lo < hi) {
let mid = Math.floor(lo + (hi - lo) / 2);
if (a[mid] < val)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
// Function to find the
// maximum number of elements
function maxNumbers(stack1, N, stack2,
M, K) {
// Take prefix of both the stack
let sumA = new Array(N + 1).fill(0);
let sumB = new Array(M + 1).fill(0);
for (let i = 0; i < N; i++)
sumA[i + 1] = sumA[i] + stack1[i];
for (let i = 0; i < M; i++)
sumB[i + 1] = sumB[i] + stack2[i];
// Calculate maxNumbers
let MaxNumbers = 0;
for (let i = 0; i <= N; i++) {
// Calculate remaining value of K
// after selecting numbers
// from 1st stack
let remValueOfK = K - sumA[i];
// If rem value of K is less than 0
// continue the loop
if (remValueOfK < 0)
continue;
// Calculate lower bound
let lowerBound
= lower_bound(sumB,
remValueOfK);
// If size of lower bound is greater
// than self stack size or
// value of lower bound element
// decrement lowerBound
if (lowerBound > M
|| sumB[lowerBound] > remValueOfK) {
lowerBound--;
}
// Store max possible numbers
let books = i + lowerBound;
MaxNumbers = Math.max(MaxNumbers, books);
}
return MaxNumbers;
}
// Driver code
let stack1 = [60, 90, 120];
let stack2 = [100, 10, 10, 200];
let K = 130;
let N = 3;
let M = 4;
let ans
= maxNumbers(stack1, N, stack2, M, K);
document.write(ans)
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA