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