C++ 用户自定义数据类型的多集合

给你Q个查询。每个查询包含一个整数k和一个人的信息，即名字、姓氏和年龄。对于每个查询，如果所有人的信息都按升序排列，我们需要输出第k个人。

注意: 如果A的名字按字典顺序小于B的名字，则人A排在人B之前。但如果名字相同，则比较姓氏，如果姓氏也相同，则比较他们的年龄。

给定: k将始终小于或等于出席人数。

示例：

输入：Q = 2 
          1 
          aa bb 10
          2 
          bb cc 10 
输出：
名字：aa 
姓氏：bb 
年龄：10 

名字：bb 
姓氏：cc 
年龄：10 

解决方法： 下面的算法用于解决上述问题。

• 基本上我们有一个人的详细信息，每个查询都要告诉我们第k个人是否按升序排列。
• 基本方法： 每个查询后，我们对列表进行排序并打印第k个人的详细信息。但如果我们使用排序来解决上述问题，则时间复杂度将为O(qqlog(q))。即每次排序的qlog(q)和q个查询。
• 优化： 我们可以改进上述问题的时间复杂度。由于插入多集合可以在log(n)中完成。
• 所以，只需创建一个多集合，用于储存结构，然后在每个查询后将人的详细信息插入我们的多集合中。
• 所以，这似乎是更好的方法。我们的总体复杂度将是O(q*log(q))。

// CPP程序用于查询第k个人，
// 按照名字的字典顺序，然后是姓氏啊，然后是年龄
#include <bits/stdc++.h>
using namespace std;
  
struct person {
    string firstName, lastName;
    int age;
};
  
// 操作符重载，使用户自定义数据类型可以使用多重集。
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;
}
  
// 定义一个函数来输出结果
void print(multiset<person>::iterator it)
{
    cout << "名字:" << it->firstName << endl;
    cout << "姓氏:" << it->lastName << endl;
    cout << "年龄: " << it->age << endl;
}
  
int main()
{
    int q = 2;
  
    // 定义一个多重集合
    multiset<person> s;
  
    // 定义person结构体变量
    person p;
  
    // 第一次查询 k=1, 名字=aa, 姓氏=bb, 年龄=10;
    int k = 1;
    p.firstName = "aa";
    p.lastName = "bb";
    p.age = 10;
  
    // 将结构体变量插入集合中
    s.insert(p);
  
    // 找到集合中第k小的元素
    multiset<person>::iterator it;
    it = s.begin();
  
    // 找到第k个元素
    std::advance(it, k - 1);
    print(it);
  
    // 第二次查询 k=2, 名字=bb, 姓氏=cc, 年龄=10;
    k = 2;
    p.firstName = "bb";
    p.lastName = "cc";
    p.age = 10;
  
    // 将结构体变量插入集合中
    s.insert(p);
  
    // 找到集合中第k小的元素
    it = s.begin();
  
    // 找到第k个元素
    std::advance(it, k - 1);
    print(it);
    return 0;
}

名字:aa
姓氏:bb
年龄:10
名字:bb
姓氏:cc
年龄:10