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;
}