Dadas dos arrays arr[] y powr[] de tamaño N y un entero K . Cada elemento arr[i] tiene su respectivo poder powr[i] . La tarea es maximizar el valor de la función dada eligiendo como máximo K elementos de la array. La función se define como:
f(N) = (arr[i 1 ] + arr[i 2 ] + arr[i 3 ]+…..arr[i n ]) * min(potencia[i 1 ], potencia[i 2 ], potencia[ i 3 ], …..powr[i n ]) donde, arr[i 1 ], arr[i 2 ], arr[i 3 ], …..arr[i n ] son los elementos elegidos.
Ejemplos:
Entrada: arr[] = {11, 10, 7, 6, 9}, powr[] = {3, 2, 4, 1, 1}, K = 2, N = 5
Salida: 54
Explicación: Elija elementos en los índices {0, 2} entonces, f(N) = (11 + 7) * min(3, 4) = 18 * 3 = 54, que es el valor máximo posible que se puede lograr eligiendo como máximo 2 elementos.Entrada: arr[] = {5, 12, 11, 9}, powr[] = {2, 1, 10, 1}, K = 3, N = 4
Salida: 110
Planteamiento: La idea es considerar cada i-ésimo elemento como la potencia mínima, para ello ordenar los elementos en orden descendente de potencia, de modo que se considere que el primer elemento tiene la potencia más alta. En todo momento trate de mantener una lista de elementos de tamaño como máximo K . Esta lista contendrá como máximo K elementos con el mayor , sin incluir el i-ésimo elemento actual. Si ya tiene una lista de tamaño K , elimine el elemento con la longitud más pequeña para que el tamaño se convierta en K – 1 , luego incluya el elemento actual en la lista, el tamaño se convierte en K y actualice rescon máximo uno. Al final, devuelve res , que es la respuesta.
- Inicialice un vector de pares v[] de tamaño N para almacenar elementos junto con su potencia.
- Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
- Asigne los valores power[i] y arr[i] como el primer y segundo valor de la array v[].
- Ordene la array v[] en orden ascendente .
- Inicialice las variables res y sum como 0 para almacenar el resultado y la suma.
- Inicializa un conjunto de pares s[] .
- Itere sobre el rango [N-1, 0] usando la variable i y realice las siguientes tareas:
- Inserte el par {v[i].segundo, i} en el conjunto s[].
- Agregue el valor de v[i].segundo a la variable sum.
- Si s.size() es mayor que K , realice las siguientes tareas:
- Inicialice la variable it como el primer elemento del conjunto s[].
- Reduzca el valor it.first de la variable sum.
- Elimina la variable it del conjunto s[].
- Establezca el valor de res como el máximo de res o sum*v[i].primero.
- Después de realizar los pasos anteriores, imprima el valor de res como respuesta.
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;
// Function to maximize the value of the
// function by choosing at most K elements
// from the given array
int maximumValue(int arr[], int powr[],
int K, int N)
{
// Vector to store the power of elements
// along with the elements in pair
vector<pair<int, int> > v(N);
// In a pair, the first position contains
// the power and the second position
// contains the element
for (int i = 0; i < N; i++) {
v[i].first = powr[i];
v[i].second = arr[i];
}
// Sort the vector according to the
// power of the elements
sort(v.begin(), v.end());
// Variable to store the answer
int res = 0;
// Variable to store the sum of
// elements
int sum = 0;
// Create a set of pairs
set<pair<int, int> > s;
// Traverse the vector in reverse order
for (int i = N - 1; i >= 0; i--) {
// Insert the element along with the
// index in pair
s.insert(make_pair(v[i].second, i));
sum += v[i].second;
// If size of set exceeds K, then
// delete the first pair in the set
// and update the sum by excluding
// the elements value from it
if (s.size() > K) {
auto it = s.begin();
sum -= it->first;
s.erase(it);
}
// Store the maximum of all sum
// multiplied by the element's
// power
res = max(res, sum * v[i].first);
}
// Return res
return res;
}
// Driver Code
int main()
{
int arr[] = { 11, 10, 7, 6, 9 };
int powr[] = { 3, 2, 4, 1, 1 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumValue(arr, powr, K, N);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
class GFG {
static class Pair {
int first;
int second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
// Function to maximize the value of the
// function by choosing at most K elements
// from the given array
public static int maximumValue(int arr[], int powr[], int K, int N) {
// Vector to store the power of elements
// along with the elements in pair
ArrayList<Pair> v = new ArrayList<Pair>();
// In a pair, the first position contains
// the power and the second position
// contains the element
for (int i = 0; i < N; i++) {
v.add(new Pair(0, 0));
v.get(i).first = powr[i];
v.get(i).second = arr[i];
}
// Sort the vector according to the
// power of the elements
Collections.sort(v, new Comparator<Pair>() {
@Override
public int compare(final Pair lhs, Pair rhs) {
return lhs.first > rhs.first ? 1 : -1;
};
});
// Variable to store the answer
int res = 0;
// Variable to store the sum of
// elements
int sum = 0;
// Create a set of pairs
HashSet<Pair> s = new HashSet<Pair>();
// Traverse the vector in reverse order
for (int i = N - 1; i >= 0; i--) {
// Insert the element along with the
// index in pair
s.add(new Pair(v.get(i).second, i));
sum += v.get(i).second;
// If size of set exceeds K, then
// delete the first pair in the set
// and update the sum by excluding
// the elements value from it
if (s.size() > K) {
Pair it = s.iterator().next();
sum -= it.first;
s.remove(it);
}
// Store the maximum of all sum
// multiplied by the element's
// power
res = Math.max(res, sum * v.get(i).first);
}
// Return res
return res;
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 11, 10, 7, 6, 9 };
int powr[] = { 3, 2, 4, 1, 1 };
int K = 2;
int N = arr.length;
System.out.println(maximumValue(arr, powr, K, N));
}
}
// This code is contributed by gfgking.
Python3
# Python 3 program for the above approach # Function to maximize the value of the # function by choosing at most K elements # from the given array def maximumValue(arr, powr, K, N): # Vector to store the power of elements # along with the elements in pair v = [[0 for x in range(2)] for y in range(N)] # In a pair, the first position contains # the power and the second position # contains the element for i in range(N): v[i][0] = powr[i] v[i][1] = arr[i] # Sort the vector according to the # power of the elements v.sort() # Variable to store the answer res = 0 # Variable to store the sum of # elements sum = 0 # Create a set of pairs s = set([]) # Traverse the vector in reverse order for i in range(N - 1, -1, -1): # Insert the element along with the # index in pair s.add((v[i][1], i)) sum += v[i][1] # If size of set exceeds K, then # delete the first pair in the set # and update the sum by excluding # the elements value from it if (len(s) > K): sum -= list(s)[0][0] list(s).remove(list(s)[0]) # Store the maximum of all sum # multiplied by the element's # power res = max(res, sum * v[i][0]) # Return res return res # Driver Code if __name__ == "__main__": arr = [11, 10, 7, 6, 9] powr = [3, 2, 4, 1, 1] K = 2 N = len(arr) print(maximumValue(arr, powr, K, N)) # This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to maximize the value of the
// function by choosing at most K elements
// from the given array
function maximumValue(arr, powr, K, N) {
// Vector to store the power of elements
// along with the elements in pair
let v = new Array(N).fill(0).map(() => []);
// In a pair, the first position contains
// the power and the second position
// contains the element
for (let i = 0; i < N; i++) {
v[i][0] = powr[i];
v[i][1] = arr[i];
}
// Sort the vector according to the
// power of the elements
v.sort();
// Variable to store the answer
let res = 0;
// Variable to store the sum of
// elements
let sum = 0;
// Create a set of pairs
let s = new Set();
// Traverse the vector in reverse order
for (let i = N - 1; i >= 0; i--) {
// Insert the element along with the
// index in pair
s.add([v[i][1], i]);
sum += v[i][1];
// If size of set exceeds K, then
// delete the first pair in the set
// and update the sum by excluding
// the elements value from it
if (s.size > K) {
let it = [...s][0];
sum -= it[0];
s.delete(it);
}
// Store the maximum of all sum
// multiplied by the element's
// power
res = Math.max(res, sum * v[i][0]);
}
// Return res
return res;
}
// Driver Code
let arr = [11, 10, 7, 6, 9];
let powr = [3, 2, 4, 1, 1];
let K = 2;
let N = arr.length;
document.write(maximumValue(arr, powr, K, N))
// This code is contributed by saurabh_jaiswal.
</script>
Producción
54
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)