Dado un entero positivo M y dos arrays arr[] y value[] de N y K enteros positivos respectivamente, la tarea es agregar cada elemento en value[] a un elemento en arr[] de tal manera que después de realizar todas las adiciones, el elemento máximo en la array es como máximo M . Si es posible hacerlo, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {5, 9, 3, 8, 7}, value[] = {1, 2, 3, 4}, M = 9
Salida: Sí
Explicación:
Agregue 1 y 3 a arr[0] maximizando a 9.
Agregar 2 y 4 a arr[2] lo maximiza a 9.
Por lo tanto, el arr final se convierte en {9, 9, 9, 8, 7}.
Entrada: arr[] = {5, 8, 3, 8, 7}, value[] = {1, 2, 3, 4}, M = 8
Salida: No
Explicación:
Agregar 1 a arr[4], 3 a arr[0] y 4 a arr[2], la array se modifica a {8, 8, 7, 8, 8}.
El elemento máximo actual en arr[] es 8.
Por lo tanto, solo es necesario agregar 2 desde value[] a cualquier elemento de arr[].
Pero, al agregar 2 a cualquier elemento en arr[], el elemento máximo en la array supera los 8.
Enfoque ingenuo:
el enfoque más simple es elegir cualquier elemento K de la array dada arr[] y agregar los valores K en la array value[] con estos valores K elegidos. ¡ Estos K valores se pueden agregar a los K números elegidos de la array arr[] en K! maneras (en el peor de los casos).
Complejidad de tiempo: O( N P K )
Enfoque eficiente:
siga los pasos a continuación para resolver el problema:
- Ordene los elementos en la array value[] en orden decreciente.
- Almacene todos los elementos de arr[] en la cola de prioridad mínima .
- Ahora extraiga el elemento mínimo (digamos X ) de la cola de prioridad y agregue los elementos de la array value[ ] a X.
- Mientras agrega valor del valor de array [] a X excede M , luego inserte el elemento X en la cola de prioridad y repita el paso anterior para el siguiente valor mínimo en la cola de prioridad.
- Si todos los elementos en value[] se agregan a algunos elementos en arr[], entonces «Sí» , de lo contrario, imprima «No» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement the // above approach #include <bits/stdc++.h> using namespace std; // Function which checks if all // additions are possible void solve(int ar[], int values[], int N, int K, int M) { // Sorting values[] in // decreasing order sort(values, values + K, greater<int>()); // Minimum priority queue which // contains all the elements // of array arr[] priority_queue<int, vector<int>, greater<int> > pq; for (int x = 0; x < N; x++) { pq.push(ar[x]); } // poss stores whether all the // additions are possible bool poss = true; for (int x = 0; x < K; x++) { // Minimum value in the // priority queue int mini = pq.top(); pq.pop(); int val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.push(val); } // If all elements are added if (poss) { cout << "Yes" << endl; } else { cout << "No" << endl; } } // Driver Code int main() { int ar[] = { 5, 9, 3, 8, 7 }; int N = 5; int values[] = { 1, 2, 3, 4 }; int K = 4; int M = 9; solve(ar, values, N, K, M); return 0; }
Java
// Java program to implement the // above approach import java.io.*; import java.util.*; class GFG{ // Function which checks if all // additions are possible static void solve(Integer ar[], Integer values[], int N, int K, int M) { // Sorting values[] in // decreasing order Arrays.sort(values, (a, b) -> b - a); // Minimum priority queue which // contains all the elements // of array arr[] PriorityQueue<Integer> pq = new PriorityQueue<>(); for(int x = 0; x < N; x++) { pq.add(ar[x]); } // poss stores whether all the // additions are possible boolean poss = true; for(int x = 0; x < K; x++) { // Minimum value in the // priority queue int mini = pq.peek(); pq.poll(); int val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.add(val); } // If all elements are added if (poss) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver Code public static void main(String args[]) { Integer ar[] = { 5, 9, 3, 8, 7 }; int N = 5; Integer values[] = { 1, 2, 3, 4 }; int K = 4; int M = 9; solve(ar, values, N, K, M); } } // This code is contributed by offbeat
Python3
# Python3 program to implement the # above approach from queue import PriorityQueue # Function which checks if all # additions are possible def solve(ar, values, N, K, M): # Sorting values[] in # decreasing order values.sort(reverse = True) # Minimum priority queue which # contains all the elements # of array arr[] pq = PriorityQueue() for x in range(N): pq.put(ar[x]); # poss stores whether all the # additions are possible poss = True; for x in range(K): # Minimum value in the # priority queue mini = pq.get(); val = mini + values[x]; # If on addition it exceeds # M then not possible if (val > M): poss = False; break; pq.put(val); # If all elements are added if (poss): print("Yes"); else: print("No"); # Driver Code if __name__=='__main__': ar = [ 5, 9, 3, 8, 7 ] N = 5; values = [ 1, 2, 3, 4 ] K = 4; M = 9; solve(ar, values, N, K, M); # This code is contributed by rutvik_56
C#
// C# Program to implement the // above approach using System; using System.Collections.Generic; class GFG { // Function which checks if all // additions are possible static void solve(int[] ar, int[] values, int N, int K, int M) { // Sorting values[] in // decreasing order Array.Sort(values); Array.Reverse(values); // Minimum priority queue which // contains all the elements // of array arr[] List<int> pq = new List<int>(); for (int x = 0; x < N; x++) { pq.Add(ar[x]); } pq.Sort(); // poss stores whether all the // additions are possible bool poss = true; for (int x = 0; x < K; x++) { // Minimum value in the // priority queue int mini = pq[0]; pq.RemoveAt(0); int val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.Add(val); pq.Sort(); } // If all elements are added if (poss) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } // Driver code static void Main() { int[] ar = { 5, 9, 3, 8, 7 }; int N = 5; int[] values = { 1, 2, 3, 4 }; int K = 4; int M = 9; solve(ar, values, N, K, M); } } // This code is contributed by divyeshrabadiya07.
Javascript
<script> // JavaScript Program to implement the // above approach // Function which checks if all // additions are possible function solve(ar, values, N, K, M) { // Sorting values[] in // decreasing order values.sort((a, b) => a - b); values.reverse(); // Minimum priority queue which // contains all the elements // of array arr[] let pq = new Array(); for (let x = 0; x < N; x++) { pq.push(ar[x]); } pq.sort((a, b) => a -b); // poss stores whether all the // additions are possible let poss = true; for (let x = 0; x < K; x++) { // Minimum value in the // priority queue let mini = pq[0]; pq.shift(); let val = mini + values[x]; // If on addition it exceeds // M then not possible if (val > M) { poss = false; break; } pq.push(val); pq.sort((a, b) => a - b); } // If all elements are added if (poss) { document.write("Yes"); } else { document.write("No"); } } // Driver code let ar = [ 5, 9, 3, 8, 7 ]; let N = 5; let values = [ 1, 2, 3, 4 ]; let K = 4; let M = 9; solve(ar, values, N, K, M); // This code is contributed by gfgking </script>
Yes
Complejidad de tiempo: O((N+K)*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA