Longest subsequence whose average is less than K | C ++ program to perform Q queries to find longest subsequence whose average is less than K ; Function to print the length for evey query ; sort array of N elements ; Array to store average from left ; Sort array of average ; number of queries ; print answer to every query using binary search ; Driver Code ; 4 queries
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubsequence ( int a [ ] , int n , int q [ ] , int m ) { sort ( a , a + n ) ; int sum = 0 ; 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 ( b , b + n ) ; for ( int i = 0 ; i < m ; i ++ ) { int k = q [ i ] ; int longest = upper_bound ( b , b + n , k ) - b ; cout << " Answer ▁ to ▁ Query " << i + 1 << " : ▁ " << longest << endl ; } } int main ( ) { int a [ ] = { 1 , 3 , 2 , 5 , 4 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int q [ ] = { 4 , 2 , 1 , 5 } ; int m = sizeof ( q ) / sizeof ( q [ 0 ] ) ; longestSubsequence ( a , n , q , m ) ; return 0 ; }