中国大学MOOC-数据结构基础习题集、08-2、The World's Richest

题目链接：http://www.patest.cn/contests/mooc-ds/08-2

题目分析：这是一道考察排序算法的一道题。题目的本身没什么难度的，首先是按资产降序排序，资产相等按年龄升序排序，年龄相等按姓名升序排序。重载一个>运算符就可以完成上述所有事情。但是有两个大数据需要特殊考虑，那就是case1和case2。一是要注意尽量使用C语言的scanf和printf以提高速度（现在提高了时间上限到400ms，是否需要还未可知）。二是某个年龄出现的次数大于一百的时候可以过滤掉（见特殊说明2），否则会超时。

特别说明：

　　1. 对结构体排序。我们这里重载operator >。具体的方法如下：

 1 struct node
 2 {
 3     string a;
 4     int b, c;
 5     node(string x, int y, int z):a(x), b(y), c(z) {}
 6     bool operator > (const node & p)const
 7     {
 8         if(c != p.c) // 资产不相等按资产排
 9         {
10             return c > p.c;
11         }
12         else         // 资产相等按年龄排
13         {
14             if(b != p.b) return b < p.b;
15             else     // 年龄相等按姓名排
16                 return a< p.a;
17         }
18     }
19     void output()
20     {
21         cout << a << " ";
22         printf("%d %d
", b, c);
23     }
24 };

　　2. 由于题目中M的值小于等于100，所以某个年龄出现的次数大于一百的时候可以过滤掉。如果不这样做，会超时。

1     int filter[100000];
2     int filter_num = 0;
3     int age_count[201] = {0}; //记录某个年龄出现的次数
4     for(int i=0; i<vec.size(); i++)
5     {
6         if(++age_count[ vec[i].b ] < 101)
7             filter[ filter_num++ ] = i;
8     }

代码分析：

头文件声明及结构体的定义：1~33
输入数据：34~49
对数据进行处理：50~60
处理查询，并输出结果：61~82

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <string>
 5 #include <cstdio>
 6 
 7 using namespace std;
 8 
 9 struct node
10 {
11     string a;
12     int b, c;
13     node(string x, int y, int z):a(x), b(y), c(z) {}
14     bool operator > (const node & p)const
15     {
16         if(c != p.c) // 资产不相等按资产排
17         {
18             return c > p.c;
19         }
20         else         // 资产相等按年龄排
21         {
22             if(b != p.b) return b < p.b;
23             else     // 年龄相等按姓名排
24                 return a< p.a;
25         }
26     }
27     void output()
28     {
29         cout << a << " ";
30         printf("%d %d
", b, c);
31     }
32 };
33 
34 int main()
35 {
36     int n, k;
37     cin >> n >> k;
38     vector<node> vec;
39     vector<node> ageVec[200];
40     // 输入名、年龄、资产
41     for(int i=0; i<n; i++)
42     {
43         string a;
44         int b;
45         int c;
46         cin >> a;
47         scanf("%d%d", &b, &c);
48         vec.push_back(node(a, b, c));
49     }
50     // 排资产：调用标准库中的sort函数即可
51     sort(vec.begin(), vec.end(), greater<node>());
52     // 如果没有此步骤，case1会超时
53     int filter[100000];
54     int filter_num = 0;
55     int age_count[201] = {0}; //记录某个年龄出现的次数
56     for(int i=0; i<vec.size(); i++)
57     {
58         if(++age_count[ vec[i].b ] < 101)
59             filter[ filter_num++ ] = i;
60     }
61     // 处理查询
62     for(int i=0; i<k; i++)
63     {
64         int m, low, high;
65         int mcount = 0;
66         scanf("%d%d%d", &m, &low, &high);
67         cout << "Case #" << i+1 << ":" << endl;
68         for(int j=0; j<filter_num && mcount<m; j++)
69         {
70             int age = vec[ filter[j] ].b;
71             if(age >= low && age <= high)
72             {
73                 mcount++;
74                 cout<<vec[ filter[j] ].a<<" ";
75                 printf("%d %d
",vec[filter[j]].b,vec[filter[j]].c);
76             }
77         }
78         if(mcount == 0)
79             cout << "None" << endl;
80     }
81     return 0;
82 }

AC成果：