Dadas dos arrays apples[] y days[] que representan el número de manzanas que produce un árbol de manzanas y el número de días que estas manzanas son comestibles desde el i -ésimo día respectivamente, la tarea es encontrar el número máximo de manzanas que una persona puede comer si la persona puede comer como máximo una manzana en un día.
Ejemplos
Entrada: manzanas[] = { 1, 2, 3, 5, 2 }, días[] = { 3, 2, 1, 4, 2 }
Salida: 7
Explicación:
el primer día, la persona come la manzana producida por apple árbol en el 1er día.
El segundo día , la persona come la manzana producida por el manzano el segundo día .
En el 3er día , la persona come la manzana producida por el manzano en el 2do día. En el día
4 al 7 , la persona come la manzana producida por el manzano en el día 4 .Entrada: manzanas[] = { 3, 0, 0, 0, 0, 2 }, días[] = { 3, 0, 0, 0, 0, 2 }
Salida: 5
Planteamiento: La idea es comer las manzanas que tengan la fecha de vencimiento más cercana. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de prioridad para almacenar el recuento de manzanas producidas en el i -ésimo día y la fecha de caducidad de esas manzanas.
- Recorra ambos arreglos e inserte el conteo de manzanas y la fecha de vencimiento de esas manzanas producidas por el manzano en el i -ésimo día.
- Compruebe si la fecha de caducidad del elemento superior de la cola de prioridad ha caducado o no. Si se encuentra que es cierto, extraiga los elementos de la cola de prioridad .
- De lo contrario, incremente el conteo máximo y disminuya el conteo de manzanas de la cola de prioridad .
- Finalmente, imprima el conteo máximo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number of apples
// a person can eat such that the person eat
// at most one apple in a day.
int cntMaxApples(vector<int> apples, vector<int> days)
{
// Stores count of apples and number
// of days those apples are edible
typedef pair<int, int> P;
// Store count of apples and number
// of days those apples are edible
priority_queue<P, vector
<p>, greater
<p> > pq;
// Stores indices of the array
int i = 0;
// Stores count of days
int n = apples.size();
// Stores maximum count of
// edible apples
int total_apples = 0;
// Traverse both the arrays
while (i < n || !pq.empty()) {
// If top element of the apple
// is not already expired
if (i < n && apples[i] != 0) {
// Insert count of apples and
// their expiration date
pq.push({ i + days[i] - 1, apples[i] });
}
// Remove outdated apples
while (!pq.empty() && pq.top().first < i) {
pq.pop();
}
// Insert all the apples produces by
// tree on current day
if (!pq.empty()) {
// Stores top element of pq
auto curr = pq.top();
// Remove top element of pq
pq.pop();
// If count of apples in curr
// is greater than 0
if (curr.second > 1) {
// Insert count of apples and
// their expiration date
pq.push({ curr.first,
curr.second - 1 });
}
// Update total_apples
++total_apples;
}
// Update index
++i;
}
return total_apples;
}
// Driver Code
int main()
{
vector<int> apples = { 1, 2, 3, 5, 2 };
vector<int> days = { 3, 2, 1, 4, 2 };
cout << cntMaxApples(apples, days);
return 0;
}
Python3
# Python3 program of the above approach # Function to find the maximum number of apples # a person can eat such that the person eat # at most one apple in a day. def cntMaxApples(apples, days) : # Store count of apples and number # of days those apples are edible pq = [] # Stores indices of the array i = 0 # Stores count of days n = len(apples) # Stores maximum count of # edible apples total_apples = 0 # Traverse both the arrays while (i < n or len(pq) > 0) : # If top element of the apple # is not already expired if (i < n and apples[i] != 0) : # Insert count of apples and # their expiration date pq.append([i + days[i] - 1, apples[i]]) pq.sort() # Remove outdated apples while (len(pq) > 0 and pq[0][0] < i) : pq.pop(0) # Insert all the apples produces by # tree on current day if (len(pq) > 0) : # Stores top element of pq curr = pq[0] # Remove top element of pq pq.pop(0) # If count of apples in curr # is greater than 0 if (len(curr) > 1) : # Insert count of apples and # their expiration date pq.append([curr[0], curr[1] - 1]) pq.sort() # Update total_apples total_apples += 1 # Update index i += 1 return total_apples apples = [ 1, 2, 3, 5, 2 ] days = [ 3, 2, 1, 4, 2 ] print(cntMaxApples(apples, days)) # This code is contributed by divyesh072019
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the maximum number of apples
// a person can eat such that the person eat
// at most one apple in a day.
static int cntMaxApples(int[] apples, int[] days)
{
// Store count of apples and number
// of days those apples are edible
List<Tuple<int,int>> pq = new List<Tuple<int,int>>();
// Stores indices of the array
int i = 0;
// Stores count of days
int n = apples.Length;
// Stores maximum count of
// edible apples
int total_apples = 0;
// Traverse both the arrays
while (i < n || pq.Count > 0) {
// If top element of the apple
// is not already expired
if (i < n && apples[i] != 0) {
// Insert count of apples and
// their expiration date
pq.Add(new Tuple<int,int>(i + days[i] - 1, apples[i]));
pq.Sort();
}
// Remove outdated apples
while (pq.Count > 0 && pq[0].Item1 < i) {
pq.RemoveAt(0);
}
// Insert all the apples produces by
// tree on current day
if (pq.Count > 0) {
// Stores top element of pq
Tuple<int,int> curr = pq[0];
// Remove top element of pq
pq.RemoveAt(0);
// If count of apples in curr
// is greater than 0
if (curr.Item2 > 1) {
// Insert count of apples and
// their expiration date
pq.Add(new Tuple<int,int>(curr.Item1, curr.Item2 - 1));
pq.Sort();
}
// Update total_apples
++total_apples;
}
// Update index
++i;
}
return total_apples;
}
// Driver code
static void Main() {
int[] apples = { 1, 2, 3, 5, 2 };
int[] days = { 3, 2, 1, 4, 2 };
Console.Write(cntMaxApples(apples, days));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program of the above approach
// Function to find the maximum number of apples
// a person can eat such that the person eat
// at most one apple in a day.
function cntMaxApples(apples, days) {
// Store count of apples and number
// of days those apples are edible
let pq = []
// Stores indices of the array
let i = 0
// Stores count of days
let n = apples.length;
// Stores maximum count of
// edible apples
let total_apples = 0
// Traverse both the arrays
while (i < n || pq.length > 0) {
// If top element of the apple
// is not already expired
if (i < n && apples[i] != 0) {
// Insert count of apples and
// their expiration date
pq.push([i + days[i] - 1, apples[i]])
pq.sort()
}
// Remove outdated apples
while (pq.length > 0 && pq[0][0] < i) {
pq.shift()
}
// Insert all the apples produces by
// tree on current day
if (pq.length > 0) {
// Stores top element of pq
curr = pq[0]
// Remove top element of pq
pq.shift()
// If count of apples in curr
// is greater than 0
if (curr.length > 1) {
// Insert count of apples and
// their expiration date
pq.push([curr[0], curr[1] - 1])
pq.sort()
}
// Update total_apples
total_apples += 1
}
// Update index
i += 1
}
return total_apples
}
let apples = [1, 2, 3, 5, 2]
let days = [3, 2, 1, 4, 2]
document.write(cntMaxApples(apples, days))
// This code is contributed by Saurabh Jaiswal
</script>
Producción:
7
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por RitvikSangwan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA