排序（需优化）
题目大意
给出n个人的姓名、年龄和拥有的钱，然后进行k次查询，每次查询输出在年龄区间内的财富值的从大到小的前m个人的信息。如果财富值相同就就先输出年龄小的，如果年龄相同就把名字按照字典序排序输出。
思路
不能先排序然后根据每一个条件再新建一个数组、对新数组排序的方法，这样测试点2会超时。（排序是非常耗时的，所以排序用得越少越好，尽量只排一次，然后用空间换时间） 而可以注意到，n和m的值悬殊，n有10的5次方，m却只有100个。所以先把所有的人按照财富值排序，再建立一个数组book标记每个年龄段拥有的人的数量，遍历数组并统计相应年龄的人数，当前年龄的人的数量不超过100的时候压入新的数组，多出来的不要压入新数组中（也就是说只取每个年龄的前100名），再从这个新的数组里面取符合相应年龄的人的信息。这样就把排序转化为了查找。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAX 100002
struct node {
char name[10];
int age, worth;
};
vector<node>people, temp, ans;
int book[MAX] = { 0 };
bool cmp(node a, node b) {
if (a.worth != b.worth)return a.worth > b.worth;
else if (a.age != b.age)return a.age < b.age;
else return strcmp(a.name, b.name) < 0;
}
int main() {
int n, k, m, amin, amax;
scanf("%d %d", &n, &k);
people.resize(n);
for (int i = 0; i < n; i++)
scanf("%s %d %d", people[i].name, &people[i].age, &people[i].worth);
sort(people.begin(), people.end(), cmp);
for (int i = 0; i < n; i++) {
if (book[people[i].age] < 100) {
book[people[i].age]++;
temp.push_back(people[i]);
}
}
for (int i = 0; i < k; i++) {
ans.clear();
scanf("%d %d %d", &m, &amin, &amax);
if (i != 0)printf("\n");
printf("Case #%d:", i + 1);
for (int j = 0; j < temp.size(); j++) {
if (temp[j].age >= amin && temp[j].age <= amax && ans.size() < m) {
ans.push_back(temp[j]);
}
}
if (ans.size() == 0)printf("\nNone");
for (int j = 0; j < ans.size(); j++) {
printf("\n%s %d %d", ans[j].name, ans[j].age, ans[j].worth);
}
}
return 0;
}
