Dada una array arr[] que contiene una permutación de los primeros N números naturales. En una operación, elimine un par (X, Y) de la array e inserte (X + Y + 1) / 2 en la array . La tarea es encontrar el elemento de array más pequeño que puede quedar en la array realizando la operación dada exactamente N – 1 veces y los N – 1 pares. Si existen varias soluciones, imprima cualquiera de ellas.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: {2}, { (2, 4), (3, 3), (1, 3) }
Explicación:
Selección de un par (arr[1] , arr[3]) modifica el arreglo arr[] = {1, 3, 3}
Seleccionando un par(arr[1], arr[2]) modifica el arreglo arr[] = {1, 3}
Seleccionando un par( arr[0], arr[1]) modifica el arreglo arr[] = {2}
Por lo tanto, el elemento más pequeño que queda en el arreglo = {2} y los pares que se pueden seleccionar son {(2, 4), (3, 3), (1, 3)}.Entrada: arr[] = {3, 2, 1}
Salida: {2}, { (3, 2), (3, 1) }
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Inicialice una array, diga pairsArr[] para almacenar todos los pares que se pueden seleccionar realizando las operaciones dadas.
- Cree una cola de prioridad , diga pq para almacenar todos los elementos de la array en la cola de prioridad.
- Atraviese pq mientras el conteo de elementos que quedan en pq es mayor que 1 y en cada operación extraiga los dos elementos superiores (X, Y) de pq , almacene (X, Y) en pairsArr[] e inserte un elemento que tenga el valor (X + Y + 1) / 2 en pq .
- Finalmente, imprima el valor del elemento que queda en pq y pairsArr[] .
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 to print the smallest element left
// in the array and the pairs by given operation
void smallestNumberLeftInPQ(int arr[], int N)
{
// Stores array elements and return
// the minimum element of arr[] in O(1)
priority_queue<int> pq;
// Stores all the pairs that can be
// selected by the given operations
vector<pair<int, int> > pairsArr;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
pq.push(arr[i]);
}
// Traverse pq while count of elements
// left in pq greater than 1
while (pq.size() > 1) {
// Stores top element of pq
int X = pq.top();
// Pop top element of pq
pq.pop();
// Stores top element of pq
int Y = pq.top();
// Pop top element of pq
pq.pop();
// Insert (X + Y + 1) / 2 in pq
pq.push((X + Y + 1) / 2);
// Insert the pair (X, Y)
// in pairsArr[]
pairsArr.push_back({ X, Y });
}
// Print the element left in pq
// by performing the given operations
cout << "{" << pq.top() << "}, ";
// Stores count of elements
// in pairsArr[]
int sz = pairsArr.size();
// Print all the pairs that can
// be selected in given operations
for (int i = 0; i < sz; i++) {
// If i is the first
// index of pairsArr[]
if (i == 0) {
cout << "{ ";
}
// Print current pairs of pairsArr[]
cout << "(" << pairsArr[i].first
<< ", " << pairsArr[i].second << ")";
// If i is not the last index
// of pairsArr[]
if (i != sz - 1) {
cout << ", ";
}
// If i is the last index
// of pairsArr[]
if (i == sz - 1) {
cout << " }";
}
}
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
smallestNumberLeftInPQ(arr, N);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print the smallest element left
// in the array and the pairs by given operation
static void smallestNumberLeftInPQ(int arr[], int N)
{
// Stores array elements and return
// the minimum element of arr[] in O(1)
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) ->
Integer.compare(y, x));
// Stores all the pairs that can be
// selected by the given operations
Vector<pair > pairsArr = new Vector<>();
// Traverse the array arr[]
for (int i = 0; i < N; i++)
{
pq.add(arr[i]);
}
// Traverse pq while count of elements
// left in pq greater than 1
while (pq.size() > 1) {
// Stores top element of pq
int X = pq.peek();
// Pop top element of pq
pq.remove();
// Stores top element of pq
int Y = pq.peek();
// Pop top element of pq
pq.remove();
// Insert (X + Y + 1) / 2 in pq
pq.add((X + Y + 1) / 2);
// Insert the pair (X, Y)
// in pairsArr[]
pairsArr.add(new pair( X, Y ));
}
// Print the element left in pq
// by performing the given operations
System.out.print("{" + pq.peek()+ "}, ");
// Stores count of elements
// in pairsArr[]
int sz = pairsArr.size();
// Print all the pairs that can
// be selected in given operations
for (int i = 0; i < sz; i++) {
// If i is the first
// index of pairsArr[]
if (i == 0) {
System.out.print("{ ");
}
// Print current pairs of pairsArr[]
System.out.print("(" + pairsArr.get(i).first
+ ", " + pairsArr.get(i).second+ ")");
// If i is not the last index
// of pairsArr[]
if (i != sz - 1) {
System.out.print(", ");
}
// If i is the last index
// of pairsArr[]
if (i == sz - 1) {
System.out.print(" }");
}
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1 };
int N = arr.length;
smallestNumberLeftInPQ(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement
# the above approach
# Function to print smallest
# element left in the array
# and the pairs by given operation
def smallestNumberLeftInPQ(arr, N):
# Stores array elements and
# return the minimum element
# of arr[] in O(1)
pq = []
# Stores all the pairs that can
# be selected by the given operations
pairsArr = []
# Traverse the array arr[]
for i in range(N):
pq.append(arr[i])
pq = sorted(pq)
# Traverse pq while count of
# elements left in pq greater
# than 1
while (len(pq) > 1):
# Stores top element of pq
X = pq[-1]
del pq[-1]
# Stores top element of pq
Y = pq[-1]
# Pop top element of pq
del pq[-1]
# Insert (X + Y + 1) / 2
# in pq
pq.append((X + Y + 1) // 2)
# Insert the pair (X, Y)
# in pairsArr[]
pairsArr.append([X, Y])
pq = sorted(pq)
# Print element left in pq
# by performing the given
# operations
print("{", pq[-1], "}, ",
end = "")
# Stores count of elements
# in pairsArr[]
sz = len(pairsArr)
# Print the pairs that can
# be selected in given operations
for i in range(sz):
# If i is the first
# index of pairsArr[]
if (i == 0):
print("{ ", end = "")
# Print pairs of pairsArr[]
print("(", pairsArr[i][0], ",",
pairsArr[i][1], ")", end = "")
# If i is not the last index
# of pairsArr[]
if (i != sz - 1):
print(end = ", ")
# If i is the last index
# of pairsArr[]
if (i == sz - 1):
print(end = " }")
# Driver Code
if __name__ == '__main__':
arr = [3, 2, 1]
N = len(arr)
smallestNumberLeftInPQ(arr, N)
# This code is contributed by Mohit Kumar 29
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to print the smallest element left
// in the array and the pairs by given operation
static void smallestNumberLeftInPQ(int[] arr,
int N)
{
// Stores array elements and return
// the minimum element of []arr in O(1)
List<int> pq = new List<int>();
// Stores all the pairs that can be
// selected by the given operations
List<pair> pairsArr = new List<pair>();
// Traverse the array []arr
for(int i = 0; i < N; i++)
{
pq.Add(arr[i]);
}
pq.Sort();
pq.Reverse();
// Traverse pq while count of elements
// left in pq greater than 1
while (pq.Count > 1)
{
// Stores top element of pq
int X = pq[0];
// Pop top element of pq
pq.RemoveAt(0);
// Stores top element of pq
int Y = pq[0];
// Pop top element of pq
pq.RemoveAt(0);
// Insert (X + Y + 1) / 2 in pq
pq.Add((X + Y + 1) / 2);
pq.Sort();
pq.Reverse();
// Insert the pair (X, Y)
// in pairsArr[]
pairsArr.Add(new pair(X, Y));
}
// Print the element left in pq
// by performing the given operations
Console.Write("{" + pq[0] + "}, ");
// Stores count of elements
// in pairsArr[]
int sz = pairsArr.Count;
// Print all the pairs that can
// be selected in given operations
for(int i = 0; i < sz; i++)
{
// If i is the first
// index of pairsArr[]
if (i == 0)
{
Console.Write("{ ");
}
// Print current pairs of pairsArr[]
Console.Write("(" + pairsArr[i].first + ", " +
pairsArr[i].second + ")");
// If i is not the last index
// of pairsArr[]
if (i != sz - 1)
{
Console.Write(", ");
}
// If i is the last index
// of pairsArr[]
if (i == sz - 1)
{
Console.Write(" }");
}
}
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 3, 2, 1 };
int N = arr.Length;
smallestNumberLeftInPQ(arr, N);
}
}
// This code is contributed by aashish1995
Javascript
<script>
// JavaScript program to implement
// the above approach
class pair
{
constructor(first,second)
{
this.first = first;
this.second = second;
}
}
// Function to print the smallest element left
// in the array and the pairs by given operation
function smallestNumberLeftInPQ(arr,N)
{
// Stores array elements and return
// the minimum element of arr[] in O(1)
let pq = [];
// Stores all the pairs that can be
// selected by the given operations
let pairsArr = [];
// Traverse the array arr[]
for (let i = 0; i < N; i++)
{
pq.push(arr[i]);
}
pq.sort(function(a,b){return b-a;});
// Traverse pq while count of elements
// left in pq greater than 1
while (pq.length > 1) {
// Stores top element of pq
let X = pq[0];
// Pop top element of pq
pq.shift();
// Stores top element of pq
let Y = pq[0];
// Pop top element of pq
pq.shift();
// Insert (X + Y + 1) / 2 in pq
pq.push(Math.floor((X + Y + 1) / 2));
pq.sort(function(a,b){return b-a;});
// Insert the pair (X, Y)
// in pairsArr[]
pairsArr.push(new pair( X, Y ));
}
// Print the element left in pq
// by performing the given operations
document.write("{" + pq[0]+ "}, ");
// Stores count of elements
// in pairsArr[]
let sz = pairsArr.length;
// Print all the pairs that can
// be selected in given operations
for (let i = 0; i < sz; i++) {
// If i is the first
// index of pairsArr[]
if (i == 0) {
document.write("{ ");
}
// Print current pairs of pairsArr[]
document.write("(" + pairsArr[i].first
+ ", " + pairsArr[i].second+ ")");
// If i is not the last index
// of pairsArr[]
if (i != sz - 1) {
document.write(", ");
}
// If i is the last index
// of pairsArr[]
if (i == sz - 1) {
document.write(" }");
}
}
}
// Driver Code
let arr=[3, 2, 1 ];
let N = arr.length;
smallestNumberLeftInPQ(arr, N);
// This code is contributed by patel2127
</script>
Producción:
{2}, { (3, 2), (3, 1) }
Complejidad de tiempo: O(N * log(N))
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA