Minimice el elemento de array restante eliminando pares y reemplazándolos con su promedio

Dada una array arr[] de tamaño N , la tarea es encontrar el elemento de array restante más pequeño posible eliminando repetidamente un par, digamos (arr[i], arr[j]) de la array e insertando el valor Ceil de su promedio .

Ejemplos:

Entrada: arr[] = { 1, 2, 3 } 
Salida:  2
Explicación: 
Quitar el par (arr[1], arr[2]) de arr[] e insertar (arr[1] + arr[2] + 1 ) / 2 en arr[] modifica arr[] a { 1, 2 }. 
Quitar el par (arr[0], arr[1]) de arr[] e insertar (arr[0] + arr[1] + 1) / 2 en arr[] modifica arr[] a { 2 }. 
Por lo tanto, la salida requerida es 2.

Entrada: arr[] = { 30, 16, 40 } 
Salida: 26 
Explicación: 
Quitar el par (arr[0], arr[2]) de arr[] e insertar (arr[0] + arr[2] + 1 ) / 2 en arr[] modifica arr[] a { 16, 35 } . 
Quitar el par (arr[0], arr[1]) de arr[] e insertar (arr[0] + arr[1] + 1) / 2 en arr[] modifica arr[] a { 26 } . 
Por lo tanto, la salida requerida es 26.

Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es eliminar repetidamente el elemento de array máximo y segundo máximo e insertar su promedio. Finalmente, imprima el elemento más pequeño que queda en la array.

• Inicialice una cola de prioridad , digamos PQ , para almacenar los elementos de la array de modo que el elemento más grande esté siempre presente en la parte superior de PQ .
• Atraviese la array y almacene todos los elementos de la array en PQ .
• Iterar sobre los elementos de la cola_prioridad mientras el recuento de elementos en la cola_prioridad es mayor que 1 . En cada iteración, extraiga los dos elementos superiores de PQ e inserte el valor Ceil de su promedio.
• Finalmente, imprima el elemento que queda en PQ .

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the smallest element
// left in the array by removing pairs
// and inserting their average
int findSmallestNumLeft(int arr[], int N)
{
    // Stores array elements such that the
    // largest element present at top of PQ
    priority_queue<int> PQ;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // Insert arr[i] into PQ
        PQ.push(arr[i]);
    }
 
    // Iterate over elements of PQ while count
    // of elements in PQ greater than 1
    while (PQ.size() > 1) {
 
        // Stores largest element of PQ
        int top1 = PQ.top();
 
        // Pop the largest element of PQ
        PQ.pop();
 
        // Stores largest element of PQ
        int top2 = PQ.top();
 
        // Pop the largest element of PQ
        PQ.pop();
 
        // Insert the ceil value of average
        // of top1 and top2
        PQ.push((top1 + top2 + 1) / 2);
    }
 
    return PQ.top();
}
 
// Driver Code
int main()
{
    int arr[] = { 30, 16, 40 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    cout << findSmallestNumLeft(
        arr, N);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.PriorityQueue;
 
class GFG{
 
// Function to find the smallest element
// left in the array by removing pairs
// and inserting their average
static int findSmallestNumLeft(int arr[], int N)
{
   
    // Stores array elements such that the
    // largest element present at top of PQ
    PriorityQueue<Integer> PQ = new PriorityQueue<Integer>((a,b)->b-a);
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
        // Insert arr[i] into PQ
        PQ.add(arr[i]);
    }
 
    // Iterate over elements of PQ while count
    // of elements in PQ greater than 1
    while (PQ.size() > 1)
    {
 
        // Stores largest element of PQ
        int top1 = PQ.peek();
 
        // Pop the largest element of PQ
        PQ.remove();
 
        // Stores largest element of PQ
        int top2 = PQ.peek();
 
        // Pop the largest element of PQ
        PQ.remove();
 
        // Insert the ceil value of average
        // of top1 and top2
        PQ.add((top1 + top2 + 1) / 2);
    }
 
    return PQ.peek();
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 30, 16, 40 };
    int N = arr.length;
 
    System.out.print(findSmallestNumLeft(
        arr, N));
 
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
 
# Function to find the smallest element
# left in the array by removing pairs
# and inserting their average
def findSmallestNumLeft(arr, N):
     
    # Stores array elements such that the
    # largest element present at top of PQ
    PQ = []
 
    # Traverse the array
    for i in range(N):
         
        # Insert arr[i] into PQ
        PQ.append(arr[i])
 
    # Iterate over elements of PQ while count
    # of elements in PQ greater than 1
    PQ = sorted(PQ)
 
    while (len(PQ) > 1):
 
        # Stores largest element of PQ
        top1 = PQ[-1]
 
        # Pop the largest element of PQ
        del PQ[-1]
 
        # Stores largest element of PQ
        top2 = PQ[-1]
 
        # Pop the largest element of PQ
        del PQ[-1]
 
        # Insert the ceil value of average
        # of top1 and top2
        PQ.append((top1 + top2 + 1) // 2)
        PQ = sorted(PQ)
 
    return PQ[-1]
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 30, 16, 40 ]
    N = len(arr)
 
    print (findSmallestNumLeft(arr, N))
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GfG
{
    // Function to find the smallest element
    // left in the array by removing pairs
    // and inserting their average
    static int findSmallestNumLeft(int[] arr, int N)
    {
        // Stores array elements such that the
        // largest element present at top of PQ
        List<int> PQ = new List<int>();
      
        // Traverse the array
        for (int i = 0; i < N; i++) {
      
            // Insert arr[i] into PQ
            PQ.Add(arr[i]);
        }
         
        PQ.Sort();
        PQ.Reverse();
         
        // Iterate over elements of PQ while count
        // of elements in PQ greater than 1
        while (PQ.Count > 1) {
      
            // Stores largest element of PQ
            int top1 = PQ[0];
      
            // Pop the largest element of PQ
            PQ.RemoveAt(0);
      
            // Stores largest element of PQ
            int top2 = PQ[0];
      
            // Pop the largest element of PQ
            PQ.RemoveAt(0);
      
            // Insert the ceil value of average
            // of top1 and top2
            PQ.Add((top1 + top2 + 1) / 2);
             
            PQ.Sort();
            PQ.Reverse();
        }
      
        return PQ[0];
    }
 
  // Driver code
    public static void Main()
    {
        int[] arr = { 30, 16, 40 };
        int N = arr.Length;
      
        Console.Write(findSmallestNumLeft(arr, N));
    }
}
 
// This code is contributed by divyeshrabadiya07.

<script>
// Javascript program to implement
// the above approach
 
// Function to find the smallest element
// left in the array by removing pairs
// and inserting their average
function  findSmallestNumLeft(arr, N)
{
 
    // Stores array elements such that the
    // largest element present at top of PQ
    let PQ = [];
  
    // Traverse the array
    for (let i = 0; i < N; i++)
    {
  
        // Insert arr[i] into PQ
        PQ.push(arr[i]);
    }
     
    PQ.sort(function(a,b){return b-a;});
  
    // Iterate over elements of PQ while count
    // of elements in PQ greater than 1
    while (PQ.length > 1)
    {
  
        // Stores largest element of PQ
        let top1 = PQ[0];
  
        // Pop the largest element of PQ
        PQ.shift();
  
        // Stores largest element of PQ
        let top2 = PQ[0];
  
        // Pop the largest element of PQ
        PQ.shift();
  
        // Insert the ceil value of average
        // of top1 and top2
        PQ.push(Math.floor((top1 + top2 + 1) / 2));
        PQ.sort(function(a,b){return b-a;});
    }
  
    return PQ[0];
}
 
// Driver Code
let arr = [ 30, 16, 40];
let N = arr.length;
document.write(findSmallestNumLeft(
        arr, N));
 
// This code is contributed by unknown2108
</script>

26

Complejidad de tiempo : O (N * logN), ya que estamos usando un bucle para atravesar N veces y la operación de cola de prioridad tomará un tiempo logN.

Espacio auxiliar : O (N), ya que estamos usando espacio adicional para la cola de prioridad.