Elimine los elementos mínimos de la array para que max <= 2 * min

Dada una array arr , la tarea es eliminar el número mínimo de elementos tal que después de su eliminación, max(arr) <= 2 * min(arr) .

Ejemplos:

Entrada: arr[] = {4, 5, 3, 8, 3}
Salida: 1
Elimina 8 de la array.

Entrada: arr[] = {1, 2, 3, 4}
Salida: 1
Elimina 1 de la array.

Enfoque: fijemos cada valor como el valor mínimo, digamos x , y encontremos el número de términos que están en el rango [x, 2*x] . Esto se puede hacer usando sumas de prefijos, podemos usar el mapa (implementa el BST de equilibrio automático) en lugar de la array, ya que los valores pueden ser grandes. Los términos restantes que no estén en el rango [x, 2*x] deberán eliminarse. Entonces, entre todos los valores de x , elegimos el que maximiza la cantidad de términos en el rango [x, 2*x] .

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the minimum removals from 
// arr such that max(arr) <= 2 * min(arr)
int minimumRemovals(int n, int a[])
{
    // Count occurrence of each element
    map<int, int> ct;
    for (int i = 0; i < n; i++)
        ct[a[i]]++;
  
    // Take prefix sum
    int sm = 0;
    for (auto mn : ct) {
        sm += mn.second;
        ct[mn.first] = sm;
    }
  
    int mx = 0, prev = 0;
    for (auto mn : ct) {
  
        // Chosen minimum
        int x = mn.first;
        int y = 2 * x;
        auto itr = ct.upper_bound(y);
        itr--;
  
        // Number of elements that are in
        // range [x, 2x]
        int cr = (itr->second) - prev;
        mx = max(mx, cr);
        prev = mn.second;
    }
  
    // Minimum elements to be removed
    return n - mx;
}
  
// Driver Program to test above function
int main()
{
    int arr[] = { 4, 5, 3, 8, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minimumRemovals(n, arr);
    return 0;
}

# Python3 implementation of the approach
from bisect import bisect_left as upper_bound
  
# Function to return the minimum removals from
# arr such that max(arr) <= 2 * min(arr)
def minimumRemovals(n, a):
      
    # Count occurrence of each element
    ct = dict()
    for i in a:
        ct[i] = ct.get(i, 0) + 1
  
    # Take prefix sum
    sm = 0
    for mn in ct:
        sm += ct[mn]
        ct[mn] = sm
  
    mx = 0
    prev = 0;
    for mn in ct:
  
        # Chosen minimum
        x = mn
        y = 2 * x
        itr = upper_bound(list(ct), y)
  
        # Number of elements that are in
        # range [x, 2x]
        cr = ct[itr] - prev
        mx = max(mx, cr)
        prev = ct[mn]
  
    # Minimum elements to be removed
    return n - mx
  
# Driver Code
arr = [4, 5, 3, 8, 3]
n = len(arr)
print(minimumRemovals(n, arr))
  
# This code is contributed by Mohit Kumar

1