Dados dos números enteros positivos N y K , inicialice una array vacía arr[] y Q número de consultas de los siguientes dos tipos:
- addInteger(x): inserta el elemento X en la array arr[] . Si el tamaño de la array es mayor que N , elimine el elemento del principio de la array .
- calculeSpecialAverage(): encuentre el promedio de los elementos de la array después de eliminar los primeros K elementos más pequeños y más grandes . Si el tamaño de la array es menor que N , imprima -1 .
La tarea es procesar las consultas dadas e imprimir los resultados en consecuencia.
Ejemplos:
Entrada: N = 3, K = 1, Q = 5, Consultas[] = { añadirEntero(4), añadirEntero(2), calcularPromedioEspecial(), añadirEntero(10), calcularPromedioEspecial() }
Salida: -1, 4
Explicación:
A continuación se muestran las consultas realizadas:
La consulta 1 es para insertar el elemento 4 en la array, arr[] se convierte en {4}.
La consulta 2 es para insertar el elemento 2 en la array, arr[] se convierte en {4, 2}.
La consulta 3 es para encontrar el promedio. Dado que el tamaño de la array es menor que N(= 3), imprima -1.
La consulta 4 es para insertar el elemento 10 en la array, arr[] se convierte en {4, 2, 10}.
Consulta 5es encontrar el promedio. Dado que el tamaño de la array = 3, elimine K (= 1) el elemento más pequeño, es decir, 2 y luego elimine el elemento más grande, es decir, 10. Ahora el promedio será 4/1 = 4.Entrada: N = 3, K = 1, Q = 5, Consultas[] = { añadirEntero(4), añadirEntero(21), calcularPromedioEspecial() }
Salida: -1
Enfoque: El problema dado se puede resolver usando el conjunto múltiple . Siga los pasos a continuación para resolver el problema:
- Inicialice tres conjuntos múltiples izquierdo, derecho y medio para almacenar los números enteros K más pequeños, K más grandes y los restantes (N – 2*K) .
- Declare un vector v de tamaño N para almacenar los últimos N enteros.
- Declare una variable entera pos para realizar un seguimiento del índice actual y una suma entera para almacenar la suma de valores en el multiconjunto medio , que es la suma deseada para calcular el promedio de (N – 2*K) enteros.
- Defina una función add para insertar un número entero en un conjunto múltiple izquierdo, medio o derecho en función de su valor. Para insertar enteros en el conjunto múltiple correcto, siga los siguientes pasos:
- Inicialmente, inserte el número entero en el conjunto múltiple izquierdo .
- Si el tamaño del conjunto múltiple izquierdo excede k , elimine el entero más grande del conjunto múltiple izquierdo e insértelo en el conjunto múltiple medio .
- Si el tamaño del conjunto múltiple medio excede (n – 2*k) , elimine el entero más grande del conjunto múltiple medio e insértelo en el conjunto múltiple derecho .
- Al eliminar y agregar enteros en el conjunto múltiple medio , mantenga el valor correcto de sum , es decir, si se elimina un número entero del conjunto múltiple medio , reste su valor de la suma y, de manera similar, si se agrega un número entero en el conjunto múltiple medio , agregue su valor a sum , para mantener el valor de la suma actualizado.
- Declare una función remove para borrar los enteros del multiconjunto izquierdo, derecho o medio .
- Si el valor del número entero es menor o igual que el entero más grande en el multiconjunto izquierdo , busque y borre el entero del multiconjunto izquierdo ; de lo contrario, búsquelo en el multiconjunto medio o derecho , según su valor.
- Si después de eliminar num , el tamaño del multiconjunto izquierdo disminuye, elimine el entero más pequeño del multiconjunto medio e insértelo en el multiconjunto izquierdo .
- De manera similar, para el conjunto múltiple medio , si el tamaño disminuye, elimine el entero más pequeño del conjunto múltiple derecho e insértelo en el conjunto múltiple medio .
- Defina una función addInteger para agregar un número entero a la secuencia actual:
- Si el número de enteros en el flujo actual (suma del tamaño del conjunto múltiple izquierdo, medio y derecho) excede n , elimine el entero en el índice pos%n .
- Llame a la función add para insertar el número entero en el conjunto múltiple izquierdo, medio o derecho , según su valor.
- Defina la función calcularPromedioEspecial para devolver el promedio especial:
- Si el número de enteros en la secuencia es menor que N , imprima -1 .
- De lo contrario, imprima el promedio como (sum/(N – 2*K)) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Special Average class
class SpecialAverage {
public:
// Three multisets to store the
// smaller K larger K and the
// remaining (n-2*k) integers
multiset<int> left, mid, right;
int n, k;
// Stores the index of current
// integer in running stream of
// integers and the sum of integers
// in mid multiset
long pos, sum;
// Array to store last n integers
vector<int> v;
// Constructor to initialize the
// values of n and k and initialize
// default values
SpecialAverage(int nvalue, int kvalue)
{
n = nvalue;
k = kvalue;
pos = 0;
sum = 0;
for (int i = 0; i < n; i++)
v.push_back(0);
}
// Add current integer in the
// multiset left, mid or right
// based on its value
void add(int num)
{
// Firstly, insert num in the
// left multiset
left.insert(num);
// Check if size of the left
// multiset is greater than k
if (left.size() > k) {
// Stores the value of the
// largest integer in the
// left multiset
int temp = *(prev(end(left)));
// Insert temp in the
// mid multiset
mid.insert(temp);
// Remove temp from the
// left multiset
left.erase(prev(end(left)));
// Add the value of temp
// to the current sum
sum += temp;
}
// Check if the size of mid
// multiset exceeds (n-2*k)
if (mid.size() > (n - 2 * k)) {
// Stores the value of the
// largest integer in the
// mid multiset
int temp = *(prev(end(mid)));
// Insert temp in the
// right multiset
right.insert(temp);
// Remove temp from the
// mid multiset
mid.erase(prev(end(mid)));
// Subtract the value of
// temp from current sum
sum -= temp;
}
}
// Remove integer from the
// multiset left, mid or right
// based on its value
void remove(int ele)
{
// If integer exists in the
// left multiset
if (ele <= *(left.rbegin()))
left.erase(left.find(ele));
// If integer exists in the
// mid multiset
else if (ele <= *(mid.rbegin())) {
// Subtract the value of
// integer from current sum
sum -= ele;
mid.erase(mid.find(ele));
}
// If integer exists in the
// right multiset
else
right.erase(right.find(ele));
// Balance all the multisets
// left, right and mid check
// if size of the left multiset
// is less than k
if (left.size() < k) {
// Stores the value of
// smallest integer
// in mid multiset
int temp = *(mid.begin());
// Insert temp in the
// left multiset
left.insert(temp);
// Remove temp from the
// mid multiset
mid.erase(mid.begin());
// Subtract the value of
// temp from current sum
sum -= temp;
}
// Check if the size of mid
// multiset becomes lesser
// than (n-2*k)
if (mid.size() < (n - 2 * k)) {
// Stores the value of
// smallest integer in
// right multiset
int temp = *(right.begin());
// Insert temp in the
// mid multiset
mid.insert(temp);
// Remove temp from the
// right multiset
right.erase(right.begin());
// Add the value of temp
// to the current sum
sum += temp;
}
}
// Function to add integer to
// the current stream
void addInteger(int num)
{
// Check if the total number
// of elements in stream > n
if (pos >= n)
// Call the function to
// remove extra integer
remove(v[pos % n]);
// Insert the current integer
// in the array v
v[(pos++) % n] = num;
// Call the function to add
// the current integer in left,
// mid or right multiset
// based on its value
add(num);
}
// Function to calculate the
// special average
int calculateSpecialAverage()
{
// Check if the total number
// of elements is greater than
// or equal to n
if (pos >= n)
// Return desired average
return ((double)sum) / (n - 2 * k);
return -1;
}
};
// Function to process all the queries
void processQueries(int n, int k)
{
// Create an object of the class
SpecialAverage* avg
= new SpecialAverage(n, k);
// Add integer Query
avg->addInteger(4);
avg->addInteger(2);
// Find average Query
cout << avg->calculateSpecialAverage()
<< endl;
// Add integer Query
avg->addInteger(10);
// Find average Query
cout << avg->calculateSpecialAverage()
<< endl;
}
// Driver Code
int main()
{
int N = 3, K = 1;
processQueries(N, K);
return 0;
}
Producción:
-1 4
Complejidad de tiempo: O(log N) para addInteger() y O(1) para calculeSpecialAverage( )
Espacio auxiliar: O(N)