PAT甲级1055The World's Richest

Posted on | | Visitors:
Words count in article: 1,068 字 | Reading time ≈ 5 分

[toc]

题目介绍

  • 题目链接

    https://pintia.cn/problem-sets/994805342720868352/problems/994805421066272768

  • 题目考点

    排序，重点在时间复杂度优化上

  • 题目难度

    PAT甲级25分

  • 题目大意

    给出N个人，请找出指定年龄范围内最有钱的M个人、

  • 输入

    • N：正整数，不超过100000，人的数量
    • K：正整数，不超过1000，查询的数量
    • N个人：每行包括名字（不包含空格、最多8个字符的字符串）、年龄（范围(0,200]）、净值（范围为±1e6）
    • K次查询：M（筛选最有钱的几个人，不超过100）、年龄范围[Amin,Amax]

  • 输出

    对于每1个查询，输出是第几个查询（从1到K），然后按净值非增序输出指定年龄范围内最有钱的M个人的信息，如果有重复则按年龄非降序输出，如果还有重复则按名字非降序输出。如果指定年龄范围内没人，就输出None。

题解一

解题思路

  • 关于指定年龄范围，只要在输出时进行年龄判断即可。

    也可以考虑在结构体比较函数中进行年龄判断，当有不符合年龄限制的人时，将其往后放。

  • 关于最有钱的人的数量，排序后只输出前M个符合年龄范围的人即可。

  • 用这个思路，测试点1和2会超时，因为这个算法的时间复杂度为$O(k\cdot n)$，最大为1e8（耗时约1秒）。

    M最大值为100，N最大值为100000，N和M差距很大，在N个人中寻找符合条件的M个人非常耗时。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// Problem: PAT Advanced 1055
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805421066272768
// Tags: 排序

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int ageMin, ageMax;

struct Person{
    string name;
    int age, wealth;
};

bool personCmp(Person& p1, Person& p2){
    if (p1.age<ageMin || p1.age>ageMax)
        return false;
    if (p2.age<ageMin || p2.age>ageMax)
        return true;
    if (p1.wealth == p2.wealth){
        if (p1.age == p2.age)
            return p1.name < p2.name;
        else
            return p1.age < p2.age;
    }
    else
        return p1.wealth > p2.wealth;
}

int main()
{
    int n,k;
    scanf("%d %d", &n, &k);
    vector<Person> people(n);
    for(int i=0; i<n; i++)
        cin >> people[i].name >> people[i].age >> people[i].wealth;
    for (int x=1, m; x<=k; x++){
        scanf("%d%d%d", &m, &ageMin, &ageMax);
        sort(people.begin(), people.end(), personCmp);
        printf("Case #%d:\n", x);
        
        int count=0;
        for(int i=0; i<n && count<m; i++)
            if (people[i].age>=ageMin && people[i].age<=ageMax){
                printf("%s %d %d\n", people[i].name.c_str(), people[i].age, people[i].wealth);
                count++;
            }
        if (count==0)
            printf("None\n");
    }
    return 0;
}

题解二

解题思路

  • 年龄范围是(0,200]，每次最多找100个人（M不超过100），那我们取出每个年龄的前100名，这样最多有20000个人。在这20000个人中查找M个人，还是快的（时间复杂度从题解一的1e8到现在的2e7），就不会超时了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Problem: PAT Advanced 1055
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805421066272768
// Tags: 排序

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int ageMin, ageMax;

struct Person{
    string name;
    int age, wealth;
};

bool personCmp(Person& p1, Person& p2){
    if (p1.wealth == p2.wealth){
        if (p1.age == p2.age)
            return p1.name < p2.name;
        else
            return p1.age < p2.age;
    }
    else
        return p1.wealth > p2.wealth;
}

int main()
{
    int n,k, selectedNum[201]={0};
    scanf("%d %d", &n, &k);
    vector<Person> people(n), selectedPeople;
    for(int i=0; i<n; i++)
        cin >> people[i].name >> people[i].age >> people[i].wealth;
    sort(people.begin(), people.end(), personCmp);
    for(int i=0; i<n; i++)
        if (selectedNum[people[i].age] < 100){
            selectedPeople.push_back(people[i]);
            selectedNum[people[i].age]++;
        }
    for (int x=1, m; x<=k; x++){
        scanf("%d%d%d", &m, &ageMin, &ageMax);
        printf("Case #%d:\n", x);
        
        int count=0;
        for(int i=0; i<selectedPeople.size() && count<m; i++)
            if (selectedPeople[i].age>=ageMin && selectedPeople[i].age<=ageMax){
                printf("%s %d %d\n", selectedPeople[i].name.c_str(), selectedPeople[i].age, selectedPeople[i].wealth);
                count++;
            }
        if (count==0)
            printf("None\n");
    }
    return 0;
}

参考链接

Github（github.com）：@chouxianyu

Github Pages（github.io）：@臭咸鱼

知乎（zhihu.com）：@臭咸鱼

博客园（cnblogs.com）：@臭咸鱼

B站（bilibili.com）：@绝版臭咸鱼

微信公众号：@臭咸鱼

转载请注明出处，欢迎讨论和交流!