Dados dos arreglos A[ ] y B[ ] que consisten en N enteros, donde A i denota la cantidad de dulces del i -ésimo tipo y B i denota la prioridad del i -ésimo dulce ( cuanto mayor es el valor mayor es la prioridad ), y un número entero K , que denota el número máximo de dulces que se pueden comer en un día. Los dulces de menor prioridad no se pueden comer antes que un dulce de mayor prioridad y solo se puede comer un tipo de dulce en un día. Dada una array Q[][] que representa consultas de la forma {Q[i][0], Q[i][1] }, la tarea de cada consulta es encontrar si el dulce del tipo Q[i][0] se puede comer el día Q [i][1] o no. Escriba “ Sí ” si es posible. De lo contrario, escriba “ No ”.
Ejemplo:
Entrada: A[] = { 6, 3, 7, 5, 2 }, B[] = { 1, 2, 3, 4, 5 }, K = 3, Q[][] = { {4, 4} , {3, 16}, {2, 7} }
Salida: Sí No Sí
Explicación:
Consulta 1: Al comer dulces en el siguiente orden, los dulces del cuarto tipo se pueden comer en el cuarto día.
Día 1: Tipo 5 -> 2 unidades
Día 2: Tipo 4 -> 2 unidades
Día 3: Tipo 4 -> 2 unidades
Día 4: Tipo 4 -> 1 unidad
Consulta 2: Total dulces de tipo 5, 4, 3 = 2 + 5 + 7 = 14. Por lo tanto, incluso después de comer un dulce cada día, no dejará ningún dulce del tipo 3 para el día 16.
Consulta 3: al comer dulces en el siguiente orden, los dulces del segundo tipo se pueden comer en el 7mo dia
Día 1: Tipo 5 -> 2 unidades.
Día 2: Tipo 4 -> 3 unidades.
Día 3: Tipo 4 -> 2 unidades.
Día 4: Tipo 3 -> 3 unidades.
Día 5: Tipo 3 -> 2 unidades.
Día 6: Tipo 3 -> 2 unidades.
Día 7: Tipo 2 -> 2uds.Entrada: A[] = { 5, 2, 6, 4, 1 }, B[] = { 2, 1, 3, 5, 4 }, K = 4, Q[][] = { {2, 17} , {5, 6} }
Salida: Sí No
Enfoque: La idea para resolver este problema es mantener una ventana para cada tipo dulce. Esta ventana contendrá básicamente el límite inferior y el límite superior de los días, dentro de los cuales se puede comer un dulce de ese tipo usando las siguientes condiciones:
- Para el límite inferior de la ventana , considere los días mínimos necesarios para completar todos los dulces de mayor prioridad, es decir, reste el mínimo (K, cantidad restante) de un dulce de un tipo de cada día.
- Para el límite superior de la ventana , considere los días máximos para completar todos los dulces de mayor prioridad, es decir, la suma de todos los dulces de mayor prioridad.
Una vez que la ventana esté preparada para cada tipo, simplemente verifique para cada consulta si el día dado se encuentra dentro de la ventana o no. Siga los pasos a continuación para resolver el problema:
Pasos:
- Mantenga un contenedor, digamos un vector de pares v para almacenar la prioridad y la cantidad de cada tipo de dulce.
- Ordene el vector de pares en orden decreciente de prioridad .
- Inicialice dos variables, digamos lowerbound y upperbound , para almacenar los límites de la ventana para cada tipo dulce.
- Recorra el vector v y realice los siguientes pasos:
- Calcular el número máximo y mínimo de días requeridos para comer dulces del i -ésimo tipo como max_days = A[i] y min_days = ceil(A[i] / K).
- Actualizar límite superior += max_days .
- Almacene la ventana {límite inferior, límite superior} para el tipo dulce actual.
- Actualizar límite inferior += min_days .
- Una vez que se completen los pasos anteriores, recorra la array Q[][] y, para cada consulta, verifique si el día dado de un tipo dulce determinado cae dentro de la ventana {límite inferior, límite superior} de ese tipo dulce o no. Si es cierto, escriba “Sí” . De lo contrario, escriba “No” .
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 queries to check
// if a sweet of given type can be
// eaten on a given day or not
void sweetTypeOnGivenDay(int a[], int b[],
int n, int k,
vector<pair<int, int> >& q)
{
// Stores pairs {priority, quantity}
// of each sweet-type
vector<pair<int, pair<int, int> > > v;
for (int i = 0; i < n; i++)
v.push_back({ b[i], { a[i], i + 1 } });
// Sorting the order of sweets in
// decreasing order of their priority
sort(v.begin(), v.end(),
greater<pair<int, pair<int, int> > >());
// Stores the window {min_days, max_days}
// for each sweet-type
map<int, pair<int, int> > mp;
// Variables to calculate the windows
int lowerbound = 0, upperbound = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculating maximum and minimum
// number of days required to complete
// the sweets of the current type
int maxi_days = v[i].second.first;
int mini_days = v[i].second.first / k;
if (v[i].second.first % k != 0)
mini_days++;
// Creating the window and storing it
upperbound += maxi_days;
mp[v[i].second.second]
= { lowerbound, upperbound };
lowerbound += mini_days;
}
// Traversing the queries
for (int i = 0; i < q.size(); i++) {
// x: Type of sweet, y: Day
int x = q[i].first, y = q[i].second;
// Find the window for the
// sweet of type x
int e = mp[x].first;
int f = mp[x].second;
// If the given day lies
// within the window
if (y >= e && y <= f)
cout << "Yes"
<< " ";
else
cout << "No"
<< " ";
}
}
// Driver Code
int main()
{
// Quantities of sweets of each type
int A[] = { 6, 3, 7, 5, 2 };
// Priorites of each type sweet
int B[] = { 1, 2, 3, 4, 5 };
// Maximum sweet of one type
// that can be eaten on a day
int K = 3;
// Queries
vector<pair<int, int> > Queries
= { { 4, 4 }, { 3, 16 }, { 2, 7 } };
// Calculating number of types
int n = sizeof(A) / sizeof(A[0]);
sweetTypeOnGivenDay(A, B, n, K, Queries);
}
Java
// Java implementation of the above approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
class GFG
{
static class Pair<K, V>
{
K first;
V second;
public Pair(K first, V second)
{
this.first = first;
this.second = second;
}
public static <K, V> Pair<K, V> of(K first, V second)
{
return new Pair<>(first, second);
}
}
// Function to find queries to check
// if a sweet of given type can be
// eaten on a given day or not
static void sweetTypeOnGivenDay(int a[], int b[],
int n, int k,
ArrayList<Pair<Integer, Integer>> q)
{
// Stores pairs {priority, quantity}
// of each sweet-type
ArrayList<Pair<Integer, Pair<Integer, Integer>>> v = new ArrayList<>();
for (int i = 0; i < n; i++)
v.add(Pair.of(b[i], Pair.of(a[i], i + 1)));
// Sorting the order of sweets in
// decreasing order of their priority
Collections.sort(v, new Comparator<Pair<Integer, Pair<Integer, Integer>>>() {
@Override
public int compare(Pair<Integer, Pair<Integer, Integer>> a, Pair<Integer, Pair<Integer, Integer>> b) {
if (a.first == b.first) {
if (a.second.first == b.second.first) {
return b.second.second - a.second.second;
}
return b.second.first - a.second.first;
}
return b.first - a.first;
}
});
// Stores the window {min_days, max_days}
// for each sweet-type
Map<Integer, Pair<Integer, Integer>> mp = new HashMap<>();
// Variables to calculate the windows
int lowerbound = 0, upperbound = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculating maximum and minimum
// number of days required to complete
// the sweets of the current type
int maxi_days = v.get(i).second.first;
int mini_days = v.get(i).second.first / k;
if (v.get(i).second.first % k != 0)
mini_days++;
// Creating the window and storing it
upperbound += maxi_days;
mp.put(v.get(i).second.second, Pair.of(lowerbound, upperbound));
lowerbound += mini_days;
}
// Traversing the queries
for (int i = 0; i < q.size(); i++)
{
// x: Type of sweet, y: Day
int x = q.get(i).first, y = q.get(i).second;
// Find the window for the
// sweet of type x
int e = mp.get(x).first;
int f = mp.get(x).second;
// If the given day lies
// within the window
if (y >= e && y <= f)
System.out.println("Yes ");
else
System.out.println("No ");
}
}
// Driver Code
public static void main(String[] args)
{
// Quantities of sweets of each type
int A[] = { 6, 3, 7, 5, 2 };
// Priorites of each type sweet
int B[] = { 1, 2, 3, 4, 5 };
// Maximum sweet of one type
// that can be eaten on a day
int K = 3;
// Queries
ArrayList<Pair<Integer, Integer>> Queries = new ArrayList<>(
Arrays.asList(Pair.of(4, 4), Pair.of(3, 16), Pair.of(2, 7)));
// Calculating number of types
int n = A.length;
sweetTypeOnGivenDay(A, B, n, K, Queries);
}
}
// This code is contributed by sanjeev2552
Yes No Yes
Complejidad temporal: O(N logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ArifShaikh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA