[PAT解题报告] The World's Richest

简单题，就是排序……

每个人有三个属性：年龄，财富，姓名。

题目要求：输出一个年龄段范围内财富最多的m个人。

主要是查询有多组，所以我们不能反复排序。但是m <= 100，所以我们把每个年龄财富财富最多的（至多）100个人保存下来就可以了。最多10^5人，查询最多10^3个，所以除去排序，复杂度不过是10 ^ 8 ，可以接受。

排序要排两次：
先按照年龄、财富、姓名的顺序排序，这样年龄相同的人在一起，并且财富是由大到小的，我们对每个年龄的人取财富前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