Encuentra elementos K con los valores más bajos

Dada una lista de elementos y sus valores. La tarea es encontrar k artículos con el valor más bajo. Es posible que dos ítems tengan el mismo valor, en ese caso se le dará mayor prioridad al ítem cuyo nombre viene primero (lexicográficamente).

Ejemplos:

Input : items[] = {Bat, Gloves, Wickets, Ball}, 
        values[] = {100, 50, 200, 100}
        k = 2
Output : Gloves Ball
Explanation : 
Gloves has the lowest value.
Ball and Bat has the same value but Ball comes first lexicographically.

Enfoque:
esta pregunta se puede resolver eligiendo los elementos con avidez de acuerdo con los valores. Ordenaremos la lista de elementos en el orden ascendente de los valores y, en el caso de los mismos valores, los elementos se ordenarán en orden lexicográfico creciente.
Almacenaremos los datos en forma de pares en un vector y usaremos una función de clasificación incorporada con una función de compactación booleana que se usará para comparar dos elementos.

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

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
  
// Boolean Comparator Function
// to compare two pairs of item-value
bool comp(pair<string, int> A, pair<string, int> B)
{
    // Compare the name if the values are equal
    if (A.second == B.second)
        return A.first < B.first;
  
    // Else compare values
    return A.second < B.second;
}
  
// Driver code
int main()
{
    int k = 2;
    int n = 3;
  
    // Store data in a vector of Item-Value Pair
    vector<pair<string, int> > items;
  
    // inserting items-value pairs in the vector
    items.push_back(make_pair("Bat", 100));
    items.push_back(make_pair("Gloves", 50));
    items.push_back(make_pair("Wickets", 200));
    items.push_back(make_pair("Ball", 100));
  
    // Sort items using Inbuilt function
    sort(items.begin(), items.end(), comp);
  
    // Print top k values
    // or if n is less than k
    // Print all n items
    for (int i = 0; i < min(n, k); ++i) {
        cout << items[i].first << '\n';
    }
  
    return 0;
}

Producción :

Gloves
Ball

Complejidad del tiempo – O(NlogN)

Optimización adicional: podemos usar el método basado en montones para encontrar k elementos más grandes de manera eficiente.