PAT甲级-1055 The World‘s Richest

题目

题目大意

输入给出富人的总数以及富人的姓名、年龄、财富，接下来的k行给出需要排序的个数，每个排序要求输出m个富人，并且限制了年龄段，[Amin, Amax]。要求输出所有的排序。如果满足年龄段的人数为0，就输出None。如果富人财富相同，年龄小的优先输出，如果年龄也相同，名字字母序小的优先输出。

思路

本来我的思路是用结构体存储完整个富人信息后，再用for循环遍历每个条件，筛选出符合年龄段的人存储到一个新数组中，再在这个新数组中排序，最后输出结果。但是测试点2运行超时，核心代码如下。

这个新数组v2在for循环中不断迭代，一直开新的空间，比较占内存，然后我又将v2放到for循环的外面，每次遍历的时候都用clear()将v2清空，但是还是超时。这里我没有想到的是，题目中的n值是很大的，10的6次方，但是要求输出的值只有m<=100个。（做题的过程中，把题中的m当成k了，然后把m弄成num了，这里没看好题）所以不能将n个全存数组后才输出，应该一边判断是否在年龄段中一边输出，当输出的数量达到要求后，再break见好就收。因此要在for循环之前就将全部的数组排序，然后在循环内遍历排序好的数组，找到符合年龄段的元素后输出。v2数组也就没有存在的必要了。另外，我把vector改成了int，速度应该能更快一点。

代码

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

struct man{
    string name;
    int age;
    int money;
}v[100003];

bool cmp(man x, man y){
    if (x.money == y.money){
        if (x.age == y.age){
            return x.name < y.name;
        }else{
            return x.age < y.age;
        }
    }else{
        return x.money > y.money;
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> v[i].name >> v[i].age >> v[i].money;
    }

    sort(v, v + n, cmp);
    for (int i = 0; i < m; i++){
        int num, amin, amax;
        cin >> num >> amin >> amax;
        cout << "Case #" << i + 1 << ":" << endl;
        int count = 0;
        for (int j = 0; j < n; j++){
            if (v[j].age >= amin && v[j].age <= amax){
                cout << v[j].name << " " << v[j].age << " " << v[j].money << endl;
                count++;
            }
            if (count == num){
                break;
            }
        }
        if (count == 0){
            cout << "None" << endl;
        }
    }

    return 0;
}