Se le dan Q consultas. Cada consulta contiene un número entero k y la información de una persona, es decir, nombre, apellido, edad. Para cada consulta, necesitamos generar la K-ésima persona entre ellas si toda la información de la persona está organizada en orden ascendente.
Nota: La persona A viene antes que la persona B si el primer nombre de A es lexicográfico más pequeño que el de B. Pero si el primer nombre es el mismo, entonces comparamos el apellido y también si el apellido también es el mismo, entonces tenemos que comparar sus edades .
Dado: K siempre será menor o igual al número de personas presentes.
Ejemplos:
Input : Q = 2
1
aa bb 10
2
bb cc 10
Output :
First name:aa
Last name:bb
Age: 10
First name:bb
Last name:cc
Age: 10
Enfoque: Se sigue el siguiente algoritmo para resolver el problema anterior.
- Básicamente, se nos proporciona el detalle de una persona con cada consulta y tenemos que decirle a la K-ésima persona si están ordenadas en orden ascendente.
- Enfoque básico: después de cada consulta, ordenamos nuestra lista y simplemente imprimimos los detalles de la k-ésima persona. Pero si resolvemos el problema anterior usando la ordenación, entonces la complejidad del tiempo será O(q*q*log(q)). es decir, O(qlog(q)) para ordenar cada vez y q consultas.
- Optimizado: podemos mejorar la complejidad del tiempo para el problema mencionado anteriormente. Como sabemos, la inserción en multiset se puede realizar en log(n).
- Por lo tanto, solo haga un conjunto múltiple que se pueda usar para almacenar la estructura, y luego, después de cada consulta, simplemente inserte los detalles de la persona en nuestro conjunto múltiple.
- Entonces, este parece ser un mejor enfoque. Nuestra complejidad general será O (q * log (q)).
// CPP program for queries to find k-th person where
// people are considered in lexicographic order of
// first name, then last name, then age
#include <bits/stdc++.h>
using namespace std;
struct person {
string firstName, lastName;
int age;
};
// operator overloading to use multiset for user
// define data type.
bool operator<(person a, person b)
{
if (a.firstName < b.firstName)
return true;
else if (a.firstName == b.firstName) {
if (a.lastName < b.lastName)
return true;
else if (a.lastName == b.lastName) {
if (a.age < b.age)
return true;
else
return false;
}
else
return false;
}
else
return false;
}
// define function for printing our output
void print(multiset<person>::iterator it)
{
cout << "First name:" << it->firstName << endl;
cout << "Last name:" << it->lastName << endl;
cout << "Age: " << it->age << endl;
}
int main()
{
int q = 2;
// define set for structure
multiset<person> s;
// declaration of person structure
person p;
// 1st Query k=1, first-name=aa, last-name=bb, age=10;
int k = 1;
p.firstName = "aa";
p.lastName = "bb";
p.age = 10;
// now insert this structure in our set.
s.insert(p);
// now find Kth smallest element in set.
multiset<person>::iterator it;
it = s.begin();
// find kth element by increment iterator by k
std::advance(it, k - 1);
print(it);
// 2nd Query k=2, first-name=bb, last-name=cc, age=10;
k = 2;
p.firstName = "bb";
p.lastName = "cc";
p.age = 10;
// now insert this structure in our set.
s.insert(p);
// now find Kth smallest element in set.
it = s.begin();
// find kth element by increment iterator by k
std::advance(it, k - 1);
print(it);
return 0;
}
First name:aa Last name:bb Age: 10 First name:bb Last name:cc Age: 10
Publicación traducida automáticamente
Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA