关于算法-数据结构: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;
}