(PAT Advanced)1055.The World's Richest (结构体排序)

结构体排序)"/>

(PAT Advanced)1055.The World's Richest (结构体排序)

原题：

Sample Input:
12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50

Sample Output:
Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None

题目分析

就是一道结构体排序的问题，只是数据量在 1 0 5 10^5 105，试了一下直接暴力排序后进行暴力搜索，居然没有超时，难以置信，贴出来看一下，使用scanf和printf代替输入输出流能节省大量数据的输入的输入输出时间，则是对于字符串会相对麻烦一点。

/* 1055 The World's Richest (25 分) */
/* 结构体排序*/
#include<string.h>
#include<map>
#include<vector>
#include<algorithm>using namespace std;typedef struct {char name[9];int age, worth;
}person;
vector<person> P;int cmp(person a, person 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;scanf("%d %d", &n, &k);person tmp;int i;for (i = 0; i < n; i++) {scanf("%s %d %d", tmp.name, &tmp.age, &tmp.worth);P.push_back(tmp);}sort(P.begin(), P.end(), cmp);// 开始查询int begin, end, m, j;for (i = 1; i <= k; i++) {printf("Case #%d:\n",i);scanf("%d %d %d", &m, &begin, &end);// 假如每次从头开始遍历，居然没有超时int cnt = 0;for (j = 0; j < n && cnt < m; j++) {if (P[j].age <= end && P[j].age >= begin) {printf("%s %d %d\n", P[j].name, P[j].age, P[j].worth);cnt++;}}if (cnt == 0) printf("None\n");}system("pause");return 0;
}

可以看到最慢的样例大概在300、400ms左右。

小优化

由于年龄在(0,200]内，每次最多输出 M ≤ 100 M \leq 100 M≤100，所以最多的存储量是 2 ∗ 1 0 4 2 * 10^4 2∗104，而输入是在 1 0 5 10^5 105，则我们可以只存储每一年龄排名在前 100 的富豪，减少极限情况下的搜索时间：

/* 1055 The World's Richest (25 分) */
/* 结构体排序*/
#include<string.h>
#include<map>
#include<vector>
#include<algorithm>using namespace std;typedef struct {char name[9];int age, worth;
}person;
vector<person> P;
int book[210]; // 每种年龄出现的次数int cmp(person a, person 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;scanf("%d %d", &n, &k);person tmp;int i;for (i = 0; i < n; i++) {scanf("%s %d %d", tmp.name, &tmp.age, &tmp.worth);P.push_back(tmp);}sort(P.begin(), P.end(), cmp);// 开始筛选数据，每个年龄只存储前100个数据vector<int> ans;for (i = 0; i < n; i++) {if (book[P[i].age] < 100) {ans.push_back(i);book[P[i].age]++;}}// 开始查询int begin, end, m, j;for (i = 1; i <= k; i++) {printf("Case #%d:\n",i);scanf("%d %d %d", &m, &begin, &end);int cnt = 0;for (j = 0; j < ans.size() && cnt < m; j++) {if (P[ans[j]].age <= end && P[ans[j]].age >= begin) {printf("%s %d %d\n", P[ans[j]].name, P[ans[j]].age, P[ans[j]].worth);cnt++;}}if (cnt == 0) printf("None\n");}system("pause");return 0;
}

可以看到极限情况下的时间缩短了。