Dado un número entero N , que representa el número de trabajadores, una array velocidad[ ] , donde velocidad[i] representa la velocidad del i -ésimo trabajador, y una array eficiencia[ ] , donde eficiencia[i] representa la eficiencia del i -ésimo trabajador, y un entero K , la tarea es seleccionar K trabajadores de tal manera que la (Suma de velocidades de todos los trabajadores) * (Eficiencia mínima de entre K trabajadores) sea la máxima posible.
Ejemplos:
Entrada: N = 6, velocidad[] = {2, 10, 3, 1, 5, 8}, eficiencia[] = {5, 4, 3, 9, 7, 2}, K = 2
Salida: 60
Explicación:
Seleccionando 2º trabajador (Velocidad = 10 y Eficiencia = 4) y 5º trabajador (Velocidad = 5 y Eficiencia = 7).
Por lo tanto, la suma máxima posible = (10 + 5) * min(4, 7) = 60Entrada: N = 6, velocidad[] = {2, 10, 3, 1, 5, 8}, eficiencia[] = {5, 4, 3, 9, 7, 2}, K = 3
Salida: 68
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice un vector de pares arr[ ] donde arr[i] es igual a {eficiencia[i], velocidad[i]} de tamaño N .
- Ordene el arr[ ] en orden decreciente de eficiencia.
- Inicialice una cola de prioridad mínima que almacene la velocidad de los trabajadores.
- Inicialice las variables, por ejemplo, SumOfSpeed = 0 y Ans = 0 .
- Iterar sobre arr[ ] y hacer lo siguiente:
- Agregue arr[i].first a SumOfSpeed
- Empuje la velocidad [i] en la cola_prioridad .
- Si el tamaño de la cola de prioridad excede K, se abre el frente de la cola de prioridad y se resta de SumOfSpeed .
- Actualice Ans como máximo de Ans y SumOfSpeed *eficiencia[i] .
- Finalmente, devuelva el Ans .
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 generate array of pairs
void generateArrayofPairs(int n, vector<int>& speed,
vector<int>& efficiency,
vector<pair<int, int> >& arr)
{
for (int i = 0; i < n; i++) {
arr[i] = { efficiency[i], speed[i] };
}
sort(arr.rbegin(), arr.rend());
}
// Function to find the maximum
// product of worker speeds and
// their minimum efficiency
int maximizePerformance(vector<int>& speed, int K,
vector<int>& efficiency)
{
int n = speed.size();
vector<pair<int, int> > arr(n);
// Function to generate
// sorted array of pairs
generateArrayofPairs(n, speed,
efficiency, arr);
// Initialize priority queue
priority_queue<int, vector<int>,
greater<int> >
pq;
// Initialize ans and sumofspeed
int ans = 0;
int SumOfSpeed = 0;
// Traversing the arr of pairs
for (auto& it : arr) {
int e = it.first;
int s = it.second;
// Updating sum of speed
SumOfSpeed += s;
// Pushing in priority queue
pq.push(s);
// If team consists of more than
// K workers
if (pq.size() > K) {
int temp = pq.top();
SumOfSpeed -= temp;
pq.pop();
}
// Taking the maximum performance
// that can be formed
ans = max(ans, SumOfSpeed * e);
}
// Finally return the ans
return ans;
}
// Driver Code
int main()
{
// Given Input
vector<int> speed = { 2, 10, 3, 1, 5, 8 };
vector<int> efficiency = { 5, 4, 3, 9, 7, 2 };
int K = 2;
// Function Call
cout << maximizePerformance(
speed, K, efficiency);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to generate array of pairs
static void generateArrayofPairs(int n, Vector<Integer> speed,
Vector<Integer> efficiency,
Vector<pair > arr)
{
for (int i = 0; i < n; i++) {
arr.insertElementAt(new pair(efficiency.elementAt(i), speed.elementAt(i)), i);
}
Collections.sort(arr, new Comparator<pair>() {
@Override public int compare(pair p1, pair p2)
{
if (p1.first != p2.first)
return (p2.first - p1.first);
return p2.second - p1.second;
}
});
}
// Function to find the maximum
// product of worker speeds and
// their minimum efficiency
static int maximizePerformance(Vector<Integer> speed, int K,
Vector<Integer> efficiency)
{
int n = speed.size();
Vector<pair > arr = new Vector<>();
// Function to generate
// sorted array of pairs
generateArrayofPairs(n, speed,
efficiency, arr);
// Initialize priority queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// Initialize ans and sumofspeed
int ans = 0;
int SumOfSpeed = 0;
// Traversing the arr of pairs
for (int i = 0; i < arr.size(); i++) {
int e = arr.elementAt(i).first;
int s = arr.elementAt(i).second;
// Updating sum of speed
SumOfSpeed += s;
// Pushing in priority queue
pq.add(s);
// If team consists of more than
// K workers
if (pq.size() > K) {
int temp = pq.peek();
SumOfSpeed -= temp;
pq.poll();
}
// Taking the maximum performance
// that can be formed
ans = Math.max(ans, SumOfSpeed * e);
}
// Finally return the ans
return ans;
}
// Driver Code
public static void main (String[] args) {
// Given Input
Vector<Integer> speed = new Vector<Integer>();
speed.add(2);
speed.add(10);
speed.add(3);
speed.add(1);
speed.add(5);
speed.add(8);
Vector<Integer> efficiency = new Vector<Integer>();
efficiency.add(5);
efficiency.add(4);
efficiency.add(3);
efficiency.add(9);
efficiency.add(7);
efficiency.add(2);
int K = 2;
// Function Call
System.out.println(maximizePerformance(
speed, K, efficiency));
}
}
// This code is contributed by Dharanendra L V.
Python3
# Python program for the above approach # Function to generate array of pairs from functools import cmp_to_key def mycmp1(a, b): if(b[0] == a[0]): return b[1] - a[1] return b[0] - a[0] def mycmp2(a,b): return b-a def generateArrayofPairs(n, speed, efficiency, arr): for i in range(n): arr[i] = [ efficiency[i], speed[i] ] arr.sort(key =cmp_to_key(mycmp1)) return arr # Function to find the maximum # product of worker speeds and # their minimum efficiency def maximizePerformance(speed, K, efficiency): n = len(speed) arr = [[0 for j in range(2)]for i in range(n)] # Function to generate # sorted array of pairs arr = generateArrayofPairs(n, speed,efficiency, arr) # Initialize priority queue pq = [] # Initialize ans and sumofspeed ans = 0 SumOfSpeed = 0 # Traversing the arr of pairs for it in arr: e = it[0] s = it[1] # Updating sum of speed SumOfSpeed += s # Pushing in priority queue pq.append(s) pq.sort(key = cmp_to_key(mycmp2)) # If team consists of more than # K workers if (len(pq) > K): temp = pq[len(pq)-1] SumOfSpeed -= temp pq.pop() # Taking the maximum performance # that can be formed ans = max(ans, SumOfSpeed * e) # Finally return the ans return ans # Driver Code # Given Input speed = [2, 10, 3, 1, 5, 8 ] efficiency = [5, 4, 3, 9, 7, 2 ] K = 2 # Function Call print(maximizePerformance(speed, K, efficiency)) # This code is contributed by shinjanpatra
Javascript
<script>
// Javascript program for the above approach
// Function to generate array of pairs
function generateArrayofPairs(n, speed, efficiency, arr)
{
for (var i = 0; i < n; i++) {
arr[i] = [ efficiency[i], speed[i] ];
}
arr.sort((a,b)=>{
if(b[0] == a[0])
return b[1] - a[1]
return b[0] - a[0];
});
return arr;
}
// Function to find the maximum
// product of worker speeds and
// their minimum efficiency
function maximizePerformance(speed, K, efficiency)
{
var n = speed.length;
var arr = Array.from(Array(n),()=>new Array(2).fill(0));
// Function to generate
// sorted array of pairs
arr = generateArrayofPairs(n, speed,
efficiency, arr);
// Initialize priority queue
var pq = [];
// Initialize ans and sumofspeed
var ans = 0;
var SumOfSpeed = 0;
// Traversing the arr of pairs
for (var it of arr) {
var e = it[0];
var s = it[1];
// Updating sum of speed
SumOfSpeed += s;
// Pushing in priority queue
pq.push(s);
pq.sort((a,b)=>b-a);
// If team consists of more than
// K workers
if (pq.length > K) {
var temp = pq[pq.length-1];
SumOfSpeed -= temp;
pq.pop();
}
// Taking the maximum performance
// that can be formed
ans = Math.max(ans, SumOfSpeed * e);
}
// Finally return the ans
return ans;
}
// Driver Code
// Given Input
var speed = [2, 10, 3, 1, 5, 8 ];
var efficiency = [5, 4, 3, 9, 7, 2 ];
var K = 2;
// Function Call
document.write(maximizePerformance(speed, K, efficiency));
// This code is contributed by rrrtnx.
</script>
Producción:
60
Complejidad temporal: O(NLogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mandeepkafle y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA