Calificación máxima posible de un concurso de codificación

Dados dos arreglos de enteros positivos Point[] , Upvote[] de tamaño N y un valor K (1 <= K <= N). La tarea es elegir al menos K elementos (Problemas) de modo que la calificación del concurso de codificación sea máxima.

Calificación del concurso: la calificación de un concurso se define como los puntos totales de todos los problemas del concurso multiplicados por los votos a favor mínimos entre todos los problemas del concurso.

Por lo tanto, Calificación = suma de puntos de los problemas del concurso * votos a favor mínimos entre los problemas del concurso.

Ejemplos:

Entrada: Point[] = {2, 10, 3, 1, 5, 8}, Upvote[] = {5, 4, 3, 9, 7, 2}, K = 2
Output: 60
Explicación:
Aquí seleccionamos 2nd y 5º problema para conseguir la máxima puntuación del concurso.
Entonces, la calificación máxima es (10 + 5) * min (4, 7) = 60

Entrada: Point[] = {2, 10, 3, 1, 5, 8}, Upvote[] = {5, 4, 3, 9, 7, 2}, K = 3
Salida: 68
Explicación:
Aquí seleccionamos 1st , 2º y 5º problema para conseguir la máxima calificación del concurso.
Entonces, la calificación máxima es (2 + 10 + 5) * min (5, 4, 7) = 68

Entrada: Point[] = {2, 20, 3, 1, 5, 8}, Upvote[] = {5, 10, 3, 9, 7, 2}, K = 4
Salida: 200
Explicación:
Aquí seleccionamos solo 2º problema para conseguir la máxima puntuación del concurso.
Una selección adicional de cualquier problema disminuye la calificación.
Entonces, la calificación máxima es 20 * 10 = 200

Acercarse :

• Pruebe el valor de cada voto positivo de mayor a menor y, al mismo tiempo, mantenga un grupo de puntos lo más grande posible, siga sumando puntos al total de puntos, si el número de problemas en el concurso excede K, despida el problema con los puntos más bajos. Esto incluye tres pasos.
  1. Ordene los problemas por su valor de votos a favor en orden decreciente.
  2. Para el índice i = 0, 1, …, K-1, empujamos los puntos al min_heap y calculamos la calificación. Solo necesitamos registrar la calificación máxima. Usamos min_heap para rastrear el problema con puntos mínimos.
  3. Para un índice i = K, K+1, …, N-1, si el punto del problema actual es mayor que la parte superior del min_heap, extraemos el elemento existente y empujamos el elemento actual en el min_heap y actualizamos el máximo clasificación.
     De esta manera, calcule la calificación máxima con respecto al problema con i-th mayores votos a favor ya que tenemos los problemas con los K puntos más grandes en el min_heap.

A continuación se muestra la implementación del enfoque anterior.

// C++ program to find the Maximum 
// Possible Rating of a Coding Contest
#include <bits/stdc++.h>
using namespace std;
  
// Function to sort all problems
// descending to upvotes
bool Comparator(pair<int, int> p1,
                pair<int, int> p2)
{
    return p1.second > p2.second;
}
  
// Function to return maximum
// rating
int FindMaxRating(int N, int Point[],
                  int Upvote[], int K)
{
    // Declaring vector of pairs
    vector<pair<int, int> > vec;
  
    // Each pair represents a problem
    // with its points and upvotes
    for (int i = 0; i < N; i++)
    {
        vec.push_back(make_pair(Point[i],
                                Upvote[i]));
    }
  
    // Step (1) - Sort problems by their 
    // upvotes value in decreasing order
    sort(vec.begin(), vec.end(), Comparator);
  
    // Declaring min_heap or priority queue 
    // to track of the problem with 
    // minimum points.
    priority_queue<int, vector<int>,
                  greater<int> > pq;
  
    int total_points = 0, max_rating = 0;
  
    // Step (2) - Loop for i = 0 to K - 1 and 
    // do accordingly
    for (int i = 0; i < K; i++)
    {
        total_points = total_points
                      + vec[i].first;
        max_rating = max(max_rating, 
                         total_points 
                         * vec[i].second);
        pq.push(vec[i].first);
    }
  
    // Step (3) - Loop for i = K to N - 1 
    // and do accordingly
    for (int i = K; i < N; i++)
    {
        if (pq.top() < vec[i].first)
        {
            total_points = total_points
                           - pq.top() 
                           + vec[i].first;
            max_rating = max(max_rating, 
                             total_points
                             * vec[i].second);
              
            pq.pop();
              
            pq.push(vec[i].first);
        }
    }
  
    return max_rating;
}
  
// Driver code
int main()
{
    int Point[] = { 2, 10, 3, 1, 5, 8 };
    int Upvote[] = { 5, 4, 3, 9, 7, 2 };
      
    int N = sizeof(Point) / sizeof(Point[0]);
    int K = 2;
  
    cout << "Maximum Rating of Coding Contest is: "
         << FindMaxRating(N, Point, Upvote, K);
  
    return 0;
}

# Python3 program to find the Maximum 
# Possible Rating of a Coding Contest 
import heapq
  
# Function to sort all problems 
# descending to upvotes
def Comparator(p1):
      
    return p1[1]
  
# Function to return maximum 
# rating 
def FindMaxRating(N, Point, Upvote, K):
      
    # Declaring vector of pairs
    vec = []
      
    # Each pair represents a problem 
    # with its points and upvotes 
    for i in range(N):
        vec.append([Point[i], Upvote[i]])
      
    # Step (1) - Sort problems by their 
    # upvotes value in decreasing order 
    vec.sort(reverse = True, key = Comparator)
      
    # Declaring min_heap or priority queue 
    # to track of the problem with 
    # minimum points. 
    pq = []
    heapq.heapify(pq)
      
    total_points, max_rating = 0, 0
      
    # Step (2) - Loop for i = 0 to K - 1 and 
    # do accordingly 
    for i in range(K):
        total_points = (total_points + 
                        vec[i][0])
          
        max_rating = max(max_rating,
                         total_points * 
                         vec[i][1])
          
        heapq.heappush(pq, vec[i][0])
      
    # Step (3) - Loop for i = K to N - 1 
    # and do accordingly 
    for i in range(K, N):
        if pq[0] < vec[i][0]:
            total_points = (total_points - 
                                   pq[0] + 
                               vec[i][0])
              
            max_rating = max(max_rating, 
                             total_points * 
                             vec[i][1])
              
            heapq.heappop(pq)
            heapq.heappush(pq, vec[i][0])
              
    return max_rating
  
# Driver code
Point = [ 2, 10, 3, 1, 5, 8 ]
Upvote = [ 5, 4, 3, 9, 7, 2 ]
  
N = len(Point)
K = 2
  
print("Maximum Rating of Coding Contest is:",
       FindMaxRating(N, Point, Upvote, K))
  
# This code is contributed by stutipathak31jan

Maximum Rating of Coding Contest is: 60

Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)