Time Limit: 200ms Memory Limit:65636 KB
题目描述
Forbes magazine publishes every year its list of billionaires based on the annual ranking of the
world's wealthiest people.Now you are supposed to simulate this job,but concentrate only on the
people in a certain range of ages.That is,given the net worths of N people,you must find the M
richest people in a given range of their ages
(《福布斯》(Forbes)杂志每年都会根据福布斯富豪榜的年度排名发布亿万富翁名单世界上最富有的人。现在你要模拟这个工作，但只专注于人们在一定的年龄范围内。也就是说，已知N个人的净资产，你必须找到M个在一定年龄范围内最富有的人)
输入格式
Each input file contains one test case.For each case,the first line contains 2 positive integers
N(≤105)-the total number of people,and K(≤10^3)-the number of queries.Then N lines follow,
each contains the name (string of no more than 8 characters without space),age (integer in (0,200]),
and the net worth(integer in [-10^6,10^6])of a person.Finally there are K lines of queries,each
contains three positive integers:M(≤100)-the maximum number of outputs,and [Amin,Amax]
which are the range of ages.All the numbers in a line are separated by a space.
(机翻：每个输入文件包含一个测试用例。对于每种情况，第一行包含2个正整数 N(≤10^5)-总人数， K(≤10^3)-查询数量 。然后之后的N行输入，一个字符串代表名称(不超过8个字符，不含空格)、年龄(0,200)、
和一个人的资产(为整数[-10^6,10^6])。最后，查询K行，输入数据包含三个正整数:M(≤100)-最大输出数，[Amin,Amax]两个整形数字（年龄范围）。一行中的所有数字都用空格隔开)
输出格式
For each query,first print in a line "Case #X:" where X is the query number starting from 1.
Then output the M richest people with their ages in the range [Amin, Amax]. Each person's
information occupies a line,in the following format:
Name Age Net_Worth
The outputs must be in non-increasing order of the net worths.In case there are equal worths.
it must be in non-decreasing order of the ages.If both worths and ages are the sa me,then the output must be in non-decreasing alphabetical order of the names.It is guaranteed that there is no two
persons share all the same of the three pieces of information.In case no one is found,output
"None".
(机翻：对于每个查询，首先打印一行“Case #X:”，其中X是从1开始的查询号。然后输出年龄在[Amin, Amax]范围内的M个最富有的人。每个人的信息占用一行，格式如下:
名字 年龄 Net_Worth
输出必须按资产值的非递增顺序排列。如果两者资产值值相等，它必须按照年龄的非递减顺序。如果资产值和年龄是相同的，那么输出必须按名称的字母顺序非递减。保证不会有两个
人们共享这三种信息，如果没有找到，输出“没有”。)
（原题即为英文题）
输入样例
12 4 //一共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名，年龄在15到45的人的信息 4 30 35 4 5 95 1 45 50
输出样例
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 Cindy76 76000 Case #4： None
题意：
给出N个人的姓名，年龄，及其拥有的财富，然后进行k次的查询。每次查询要求输出的年龄范围在[AgeL,AgeR]的财富值从大到小的前M人的信息。如果财富值相同，则年龄小的优先，如果年龄也相同则姓名的字典序小的优先。
思路：
步骤一：先将所有人按照题目的要求进行排序，cmp函数的写法类似于下面的写法：
bool cmp(Person a,Person b){ if (a.worths != b.worths) { return a.worths > b.worths; } else if (a.age != b.age) { return a.age < b.age; } else return strcmp(a.name, b.name) < 0; }
步骤二：可知题目要求输出前M名人（M在100以内），因此可以进行预处理，即将每个年龄中财富在前100名的以内的人全部存到另一个数组中（因为某个年龄中财富值在100以外的人永远不会输出），后面的查询操作均在这个数组中进行，这个预处理将显著的降低查询的复杂度，使得k次查询不会超时。(此题如果不预处理的话比较简单)
步骤三：根据题目要求k次查询，输出在给定的年龄区间[AgeL,AgeR]内的财富值前M人的信息。
如果不做预处理的话，代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100010; struct Person { char name[15];//姓名 int worths; //财富 int age; //年龄 }per[maxn]; bool cmp(Person a,Person b){//财富多，年龄小，字典序小的优先 if (a.worths != b.worths) { return a.worths > b.worths; } else if (a.age != b.age) { return a.age < b.age; } return strcmp(a.name, b.name) < 0; } int main() { int n,k; int AgeL, AgeR,m; scanf("%d%d", &n,&k); for (int i = 0; i < n; i++) {//输入N人 scanf("%s%d%d", per[i].name, &per[i].age, &per[i].worths); } sort(per, per + n, cmp); for (int i = 1; i <=k; i++) { scanf("%d%d%d",&m, &AgeL, &AgeR); printf("Case #%d:n", i); int j,num; //用j标记已经遍历的人数,用num代表输出的人数 for ( j = 0,num=0; (j < n)&&(num<m); j++) { if (per[j].age<= AgeR && per[j].age >= AgeL) { printf("%s %d %dn", per[j].name, per[j].age, per[j].worths); num++; } } if (j == n && num == 0) {//当j已经遍历了所有的人时，如果num仍然为0，则输出"None" printf("Nonen"); } } return 0; }
此时如果不做预处理的话，在二号测试点处会出现超时。
如果做预处理的话，代码如下：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 100010; int Age[maxn] = { 0 };//某年龄的人数。 struct Person { char name[15];//姓名 int worths; //财富 int age; //年龄 }per[maxn],valid[maxn]; bool cmp(Person a,Person b){//财富多，年龄小，字典序小的优先 if (a.worths != b.worths) { return a.worths > b.worths; } else if (a.age != b.age) { return a.age < b.age; } return strcmp(a.name, b.name) < 0; } int main() { int n,k; int AgeL, AgeR,m; scanf("%d%d", &n,&k); for (int i = 0; i < n; i++) {//输入N人 scanf("%s%d%d", per[i].name, &per[i].age, &per[i].worths); } sort(per, per + n, cmp);//排序 int validnum = 0; //存放到valid数组中的人数 for (int i = 0; i < n; i++) { if (Age[per[i].age] < 100) { //年龄per[i].age的人数小于100时 Age[per[i].age]++; //年龄per[i].age的人数加1 valid[validnum++] = per[i];//将per[i]加入新数组 } } for (int i = 1; i <=k; i++) { scanf("%d%d%d",&m, &AgeL, &AgeR);//前M人，年龄区间[AgeL,AgeR] printf("Case #%d:n", i); int printnum = 0; //已经输出的人数 for ( int j = 0; j < validnum&&printnum<m; j++) { if (valid[j].age<= AgeR && valid[j].age >= AgeL) { printf("%s %d %dn", valid[j].name, valid[j].age, valid[j].worths); printnum++; } } if (printnum == 0) {//当j已经遍历了所有的人时，如果num仍然为0，则输出"None" printf("Nonen"); } } return 0; }
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
