Skip to content

Latest commit

 

History

History
59 lines (50 loc) · 2.42 KB

1055. The World's Richest.md

File metadata and controls

59 lines (50 loc) · 2.42 KB

【PAT A-1055】The World's Richest

输入输出格式

输入第一行包含 2 个正整数:N 和 K,分别表示输入的总人数和查询数。然后紧接着 N 行,每行按姓名 年龄 财产的格式输入一个人的信息。接着有 K 行查询,每行包含三个正整数:M 表示最大的输出数,以及[Amin,Amax],它们构成查询的年龄范围。一行中的所有数字都用空格分隔。

针对每个查询,首先在第一行中打印Case #X:,其中X是从 1 开始的查询编号。然后输出年龄在[Amin,Amax]范围内的 M 个最富有的人,输出的每个人信息的格式为姓名 年龄 财产。输出必须按财产的非递增顺序排列;如果有相等的财产,则必须按照年龄的不降序排列;如果财产和年龄相同,则输出必须按名称的字母顺序不降序排列。保证没有两个人共享这三个信息中的所有相同信息。如果没有任何人的信息可以输出,则输出 None。

数据规模

$$N\le{10}^5,K\le{10}^3,M\le100$$

算法设计

先定义一个类 Person,其中应该包括以下几种数据成员:姓名 name、年龄 age、财产 worth。然后按题目要求对输入的所有人进行排序。针对每个查询,遍历所有人,将满足要求的人的信息进行输出即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
struct Person {
    string name;
    gg age, worth;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ki, mi, amin, amax;
    cin >> ni >> ki;
    vector<Person> p(ni);
    for (gg i = 0; i < ni; ++i) {
        cin >> p[i].name >> p[i].age >> p[i].worth;
    }
    sort(p.begin(), p.end(), [](const Person& p1, const Person& p2) {
        return tie(p2.worth, p1.age, p1.name) < tie(p1.worth, p2.age, p2.name);
    });  //排序
    for (gg i = 1; i <= ki; ++i) {
        cin >> mi >> amin >> amax;
        cout << "Case #" << i << ":\n";
        bool f = false;  //表示是否有人的信息被输出
        for (auto& j : p) {
            if (j.age >= amin and j.age <= amax) {
                cout << j.name << " " << j.age << " " << j.worth << "\n";
                --mi;
                f = true;
            }
            if (mi == 0) {  //输出了M个人信息,结束循环
                break;
            }
        }
        if (not f) {
            cout << "None\n";
        }
    }
    return 0;
}