PAT1055

题目链接:http://pat.zju.edu.cn/contests/pat-a-practise/1055

当case很大的时候，单靠排序来解决是肯定不行的，如第二个case，换一种策略，因为M最大为100，所以每个年龄的人数最大也就只需要100（按顺序排），剩下100的之后都没有用了，最极端的情况这一个年龄的M个人的排名都在剩下的年龄的人之前，这样就筛选了最多K*M条记录，对于每个查询遍历这些记录，即可。

 1 #include<cstdio>
 2 #include<vector>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct Node
 8 {
 9     char name[10];
10     int age;
11     int worth;
12 };
13 
14 bool comp2(Node n1, Node n2)
15 {
16     if(n1.worth > n2.worth)
17         return true;
18     else if(n1.worth< n2.worth)
19         return false;
20     else if(n1.age < n2.age)
21         return true;
22     else if(n1.age > n2.age)
23         return false;
24     else if(strcmp(n1.name, n2.name) < 0)
25         return true;
26     else
27         return false;
28 }
29 
30 int main()
31 {
32     int N,K;
33     scanf("%d%d", &N, &K);
34     vector<Node> list(N);
35     /*年龄分组,小于等于100个*/
36     vector<int> age(205, 0);
37     /*记录有效的结点位置,且是已排序的*/
38     vector<int> record;
39     for(int i=0; i <N; ++i)
40         scanf("%s%d%d", list[i].name, &list[i].age, &list[i].worth);
41     sort(list.begin(), list.end(), comp2);
42     for(int i=0; i<N; ++i)
43         if(age[list[i].age] <= 100)
44         {
45             ++age[list[i].age];
46             record.push_back(i);
47         }
48     for(int i=0; i<K; ++i)
49     {
50         printf("Case #%d:
", i+1);
51         int num, min, max;
52         scanf("%d%d%d", &num, &min, &max);
53         int count(0);
54         for(int j=0; j<record.size() && count<num; ++j)
55         {
56             if(list[record[j]].age <= max && list[record[j]].age >= min)
57             {
58                 ++count;
59                 printf("%s %d %d
", list[record[j]].name, list[record[j]].age, list[record[j]].worth);
60             }
61         }
62         if(count == 0)
63             printf("None
");
64     }
65     return 0;
66 }