C++ 用户自定义数据类型的多集合
给你Q个查询。每个查询包含一个整数k和一个人的信息,即名字、姓氏和年龄。对于每个查询,如果所有人的信息都按升序排列,我们需要输出第k个人。
注意: 如果A的名字按字典顺序小于B的名字,则人A排在人B之前。但如果名字相同,则比较姓氏,如果姓氏也相同,则比较他们的年龄。
给定: k将始终小于或等于出席人数。
示例:
解决方法: 下面的算法用于解决上述问题。
- 基本上我们有一个人的详细信息,每个查询都要告诉我们第k个人是否按升序排列。
- 基本方法: 每个查询后,我们对列表进行排序并打印第k个人的详细信息。但如果我们使用排序来解决上述问题,则时间复杂度将为O(qqlog(q))。即每次排序的qlog(q)和q个查询。
- 优化: 我们可以改进上述问题的时间复杂度。由于插入多集合可以在log(n)中完成。
- 所以,只需创建一个多集合,用于储存结构,然后在每个查询后将人的详细信息插入我们的多集合中。
- 所以,这似乎是更好的方法。我们的总体复杂度将是O(q*log(q))。