[PAT解题报告] The World's Richest
简单题，就是排序……
每个人有三个属性： 年龄，财富，姓名。
题目要求： 输出一个年龄段范围内财富最多的m个人。
主要是查询有多组，所以我们不能反复排序。但是m <=
100，所以我们把每个年龄财富财富最多的（至多）100个人保存下来就可以了。最多10^5人，查询最多10^3个，所以除去排序，复杂度不过是10
^ 8 ，可以接受。
排序要排两次：
先按照 年龄、 财富、 姓名的顺序排序，这样年龄相同的人在一起，并且财富是由大到小的，我们对每个年龄的人取财富前100，存起来，因为无论怎么查询，后面的人都不会被输出——最多100人嘛。而且根据题意年龄不超过200，所以这一步下来我们剩余的人最多也就是20000人了——比10^5略小。
先按照 年龄、 财富、 姓名的顺序排序，这样年龄相同的人在一起，并且财富是由大到小的，我们对每个年龄的人取财富前100，存起来，因为无论怎么查询，后面的人都不会被输出——最多100人嘛。而且根据题意年龄不超过200，所以这一步下来我们剩余的人最多也就是20000人了——比10^5略小。
第二次就是按照财富，年龄，姓名的顺序就可以了，查询结果肯定在我们排好顺序的数组里。对每个查询，我们从头遍历一次数组，看一下那个人的年龄是否在我们要的年龄段里——因为按财富排序之后年龄就乱了，并且注意最多输出m个就可以了。
注意： 没有结果的时候，输出None
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
struct node {
char name[55];
int age,worth;
};
bool cmp1(const node &a,const node &b) {
if (a.age < b.age) {
return true;
}
if (a.age > b.age) {
return false;
}
if (a.worth > b.worth) {
return true;
}
if (a.worth < b.worth) {
return false;
}
return strcmp(a.name,b.name) < 0;
}
bool cmp2(const node &a,const node &b) {
if (a.worth > b.worth) {
return true;
}
if (a.worth < b.worth) {
return false;
}
if (a.age < b.age) {
return true;
}
if (a.age > b.age) {
return false;
}
return strcmp(a.name , b.name) < 0;
}
node p[100005];
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i = 0; i < n; ++i) {
int a,w;
scanf("%s%d%d",p[i].name,&p[i].age,&p[i].worth);
}
sort(p , p + n, cmp1);
int have = 0;
for (int i = 0; i < n;) {
for (int j = i; (i < n) && (p[j].age == p[i].age); ++i) {
if (i - j < 100) {
p[have++] = p[i];
}
}
}
sort(p, p + have, cmp2);
for (int i = 1; i <= m; ++i) {
int num,from,to;
scanf("%d%d%d",&num,&from,&to);
printf("Case #%d:\n",i);
int n = 0;
for (int j = 0;(n < num) && (j < have); ++j) {
if ((p[j].age >= from) && (p[j].age <= to)) {
++n;
printf("%s %d %d\n",p[j].name,p[j].age,p[j].worth);
}
}
if (n == 0) {
puts("None");
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1055
