Dada una array de N enteros positivos y Q consultas que consisten en un entero K, la tarea es imprimir la longitud de la subsecuencia más larga cuyo promedio es menor que K.
Ejemplos:
Entrada: a[] = {1, 3, 2, 5, 4}
Consulta 1: K = 3
Consulta 2: K = 5
Salida:
4
5
Consulta 1: La subsecuencia es: {1, 3, 2, 4} o {1, 3, 2, 5}
Consulta 2: La subsecuencia es: {1, 3, 2, 5, 4}
Un enfoque ingenuo es generar todas las subsecuencias usando power-set y verificar la subsecuencia más larga cuyo promedio sea menor que K.
Complejidad de tiempo: O (2 N * N)
Un enfoque eficiente es ordenar los elementos de la array y encontrar el promedio de elementos comenzando desde la izquierda. Inserte el promedio de elementos calculados desde la izquierda en el contenedor ( vector o arrays ). Ordene el elemento del contenedor y luego use la búsqueda binaria para buscar el número K en el contenedor. La longitud de la subsecuencia más larga será, por lo tanto, el número de índice que devuelve upper_bound() para cada consulta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to perform Q queries
// to find longest subsequence whose
// average is less than K
#include <bits/stdc++.h>
using namespace std;
// Function to print the length for every query
int longestSubsequence(int a[], int n, int q[], int m)
{
// sort array of N elements
sort(a, a + n);
int sum = 0;
// Array to store average from left
int b[n];
for (int i = 0; i < n; i++) {
sum += a[i];
double av = (double)(sum) / (double)(i + 1);
b[i] = ((int)(av + 1));
}
// Sort array of average
sort(b, b + n);
// number of queries
for (int i = 0; i < m; i++) {
int k = q[i];
// print answer to every query
// using binary search
int longest = upper_bound(b, b + n, k) - b;
cout << "Answer to Query" << i + 1 << ": "
<< longest << endl;
}
}
// Driver Code
int main()
{
int a[] = { 1, 3, 2, 5, 4 };
int n = sizeof(a) / sizeof(a[0]);
// 4 queries
int q[] = { 4, 2, 1, 5 };
int m = sizeof(q) / sizeof(q[0]);
longestSubsequence(a, n, q, m);
return 0;
}
Java
// Java program to perform Q queries
// to find longest subsequence whose
// average is less than K
import java.util.Arrays;
class GFG
{
// Function to print the length for every query
static void longestSubsequence(int a[], int n,
int q[], int m)
{
// sort array of N elements
Arrays.sort(a);
int sum = 0;
// Array to store average from left
int []b = new int[n];
for (int i = 0; i < n; i++)
{
sum += a[i];
double av = (double)(sum) / (double)(i + 1);
b[i] = ((int)(av + 1));
}
// Sort array of average
Arrays.sort(b);
// number of queries
for (int i = 0; i < m; i++)
{
int k = q[i];
// print answer to every query
// using binary search
int longest = upperBound(b,0, n, k);
System.out.println("Answer to Query" + (i + 1) +": "
+ longest);
}
}
private static int upperBound(int[] a, int low, int high, int element)
{
while(low < high)
{
int middle = low + (high - low)/2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 3, 2, 5, 4 };
int n = a.length;
// 4 queries
int q[] = { 4, 2, 1, 5 };
int m = q.length;
longestSubsequence(a, n, q, m);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 program to perform Q queries to find
# longest subsequence whose average is less than K
import bisect
# Function to print the length for every query
def longestSubsequence(a, n, q, m):
# sort array of N elements
a.sort()
Sum = 0
# Array to store average from left
b = [None] * n
for i in range(0, n):
Sum += a[i]
av = Sum // (i + 1)
b[i] = av + 1
# Sort array of average
b.sort()
# number of queries
for i in range(0, m):
k = q[i]
# print answer to every query
# using binary search
longest = bisect.bisect_right(b, k)
print("Answer to Query", i + 1, ":", longest)
# Driver Code
if __name__ == "__main__":
a = [1, 3, 2, 5, 4]
n = len(a)
# 4 queries
q = [4, 2, 1, 5]
m = len(q)
longestSubsequence(a, n, q, m)
# This code is contributed by Rituraj Jain
C#
// C# program to perform Q queries
// to find longest subsequence whose
// average is less than K
using System;
class GFG
{
// Function to print the length for every query
static void longestSubsequence(int []a, int n,
int []q, int m)
{
// sort array of N elements
Array.Sort(a);
int sum = 0;
// Array to store average from left
int []b = new int[n];
for (int i = 0; i < n; i++)
{
sum += a[i];
double av = (double)(sum) / (double)(i + 1);
b[i] = ((int)(av + 1));
}
// Sort array of average
Array.Sort(b);
// number of queries
for (int i = 0; i < m; i++)
{
int k = q[i];
// print answer to every query
// using binary search
int longest = upperBound(b,0, n, k);
Console.WriteLine("Answer to Query" + (i + 1) +": "
+ longest);
}
}
private static int upperBound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low + (high - low)/2;
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
// Driver Code
static public void Main ()
{
int []a = { 1, 3, 2, 5, 4 };
int n = a.Length;
// 4 queries
int []q = { 4, 2, 1, 5 };
int m = q.Length;
longestSubsequence(a, n, q, m);
}
}
/* This code contributed by ajit */
Javascript
<script>
// Javascript program to perform Q queries
// to find longest subsequence whose
// average is less than K
// Function to print the length for every query
function longestSubsequence(a, n, q, m)
{
// sort array of N elements
a.sort(function(a, b){return a - b});
let sum = 0;
// Array to store average from left
let b = new Array(n);
for (let i = 0; i < n; i++)
{
sum += a[i];
let av = parseInt((sum) / (i + 1), 10);
b[i] = (av + 1);
}
// Sort array of average
b.sort(function(a, b){return a - b});
// number of queries
for (let i = 0; i < m; i++)
{
let k = q[i];
// print answer to every query
// using binary search
let longest = upperBound(b,0, n, k);
document.write("Answer to Query" +
(i + 1) +": "
+ longest + "</br>");
}
}
function upperBound(a, low, high, element)
{
while(low < high)
{
let middle = low +
parseInt((high - low)/2, 10);
if(a[middle] > element)
high = middle;
else
low = middle + 1;
}
return low;
}
let a = [ 1, 3, 2, 5, 4 ];
let n = a.length;
// 4 queries
let q = [ 4, 2, 1, 5 ];
let m = q.length;
longestSubsequence(a, n, q, m);
</script>
Producción:
Answer to Query1: 5 Answer to Query2: 2 Answer to Query3: 0 Answer to Query4: 5
Complejidad de tiempo: O(N*log N + M*log N)
Espacio auxiliar: O(N)