关于算法-数据结构:PAT甲级1055-The-Worlds-Richest

题目粗心：

给出N集体的姓名、年龄及其领有的财产值，而后进行K次查问。每次查问要求输入年龄范畴在[AgeL, AgeR]的财产值从大到小的前M人的信息。
如果财产值雷同，则年龄小的优先;如果年龄也雷同，则姓名的字典序小的优先。

算法思路：

总体思路就是先排序在依照要求输入后果，这里的排序能够应用排序函数，也能够应用set的自定义排序,这里抉择了第二种，无论哪一种排序办法，
最终都会导致测试超时，最要害的点在于M的取值范畴，M最大为100，阐明每一个年龄的人数最大为100，那么只须要将每一个年龄的前100名增加进新的容器中，而后再进行遍历输入就不会导致超时。

提交后果：

第一次测试：应用sort函数，导致测试点2运行超时。
第二次测试：应用set自定义排序函数，导致测试点1超时。
第三次测试：将排完序后的元素的每个年龄的前100名取出来而后遍历，测试通过。

留神点：

1、如果不将每一个年龄的前100集体取出来而后再查问的话，对于应用sort函数形式会导致测试点2超时，应用set形式会导致测试点1超时。
2、寄存每个年龄的数组大小得设置为1000以上，不然会导致测试谬误
3、暴力求解可得22分。

AC代码：

#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
#include<string>

using namespace std;

struct People{
    string name;
    int age;
    int worth;
};

struct cmp{
    bool operator()(const People &a,const People &b){
        if (a.worth!=b.worth){
            return a.worth>b.worth;
        } else if (a.age!=b.age){
            return a.age<b.age;
        } else {
            return a.name<b.name;
        }
    }
};

int main(){
    int N,K;// 总人数和查问次数
    scanf("%d %d",&N,&K);
    set<People,cmp> peoples;
    char name[20];
    People people;
    for (int i = 0; i < N; ++i) {
        scanf("%s %d %d",name,&people.age,&people.worth);
        people.name = name;
        peoples.insert(people);
    }
    // 将每个年龄的人中前100名保留到数组sorted_people中
    vector<People> sorted_people;
    int age_num[100001]; // 寄存年龄为i的人数,这里的下标不能是200，得是总人数加一，不过1000就能够通过所有测试点了
    for(auto &peo : peoples){
        if (age_num[peo.age]<100){
            ++age_num[peo.age];
            sorted_people.push_back(peo);
        }
    }
    int M,Amin,Amax;
    for (int j = 0; j < K; ++j) {
        scanf("%d %d %d",&M,&Amin,&Amax);
        // 输入后果
        printf("Case #%d:\n",j+1);
        int index = 0;
        bool printed = false;// 是否有输入
        for (auto & peo : sorted_people) {
            if (peo.age>=Amin&&peo.age<=Amax){
                if (index==M) break;
                printf("%s %d %d\n",peo.name.c_str(),peo.age,peo.worth);
                ++index;
                printed = true;
            }
        }
        if (!printed){
            printf("None\n");
        }
    }
    return 0;
}