【PAT甲级】The World's Richest
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/90213890
Problem Description：
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.
Input Specification:
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 (≤103) - 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 [−106,106]) 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.
Output Specification:
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 format
Name Age Net_WorthThe 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 same, 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.
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 50Sample 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解题思路：
结构体排序问题。先建立people结构体，包括姓名name、年龄age、净值net_worth这三个变量。自定义一个比较方法cmp：先按净值非递增排序，若净值相等则按照年龄非递减排序，若净值和年龄都相等则按照姓名非递减排序。把输入的N个富豪信息都放入到一个vector（命名为v）中，根据自定义比较方法cmp来对vector（v）进行sort，然后对vector（v）无脑for-each输出M个年龄在[Amin,Amax]这个区间的富豪即可。然而我第一次提交的代码居然直接TLE啦 25分只有18分，加上ios::sync_with_stdio(false);这条语句来取消cin和stdin之后 提交还是超时。。。。绝望? 求助晴神之后完美AC。
富豪年龄age不超过200，输出人数M不超过100，所以新建一个book用来记录每个年龄的人数，新建一个vector（命名为ans）用来存放富豪信息，每个年龄最多只记录前100个人的信息，最后对vector（ans）无脑for-each输出M个年龄在[Amin,Amax]这个区间的富豪即可。
AC代码：18分代码：
#include <bits/stdc++.h>
using namespace std;
struct people
{
string name; //姓名
int age; //年龄
int net_worth; //净值
};
bool cmp(people p1, people p2)
{
if(p1.net_worth != p2.net_worth) //先按净值非递增排序
{
return p1.net_worth > p2.net_worth;
}
else if(p1.age != p2.age) //净值相等时,按照年龄非递减排序
{
return p1.age < p2.age;
}
else //净值和年龄都相等时,按照姓名非递减排序
{
return p1.name < p2.name;
}
}
int main()
{
ios::sync_with_stdio(false); //取消cin和stdin的同步
int N,K; //总人数N、查询次数K
cin >> N >> K;
vector<people> v;
for(int i = 0; i < N; i++)
{
string name;
int age,net_worth;
cin >> name >> age >> net_worth;
v.push_back({name,age,net_worth});
}
sort(v.begin(), v.end(),cmp); //将富豪进行排序
for(int i = 1; i <= K; i++)
{
int M,Amin,Amax; //最多输出M个人,年龄区间[Amin,Amax]
cin >> M >> Amin >> Amax;
printf("Case #%d:\n",i);
int cnt = 0; //用来记录已经输出的人数
for(auto it : v)
{
if(it.age >= Amin && it.age <= Amax && cnt < M)
{
printf("%s %d %d\n",it.name.c_str(),it.age,it.net_worth);
cnt++;
}
}
if(cnt == 0)
{
printf("None\n");
}
}
return 0;
}AC代码：
#include <bits/stdc++.h>
using namespace std;
struct people
{
string name; //姓名
int age; //年龄
int net_worth; //净值
};
bool cmp(people p1, people p2)
{
if(p1.net_worth != p2.net_worth) //先按净值非递增排序
{
return p1.net_worth > p2.net_worth;
}
else if(p1.age != p2.age) //净值相等时,按照年龄非递减排序
{
return p1.age < p2.age;
}
else //净值和年龄都相等时,按照姓名非递减排序
{
return p1.name < p2.name;
}
}
int main()
{
ios::sync_with_stdio(false); //取消cin和stdin的同步
int N,K; //总人数N、查询次数K
cin >> N >> K;
vector<people> v;
for(int i = 0; i < N; i++)
{
string name;
int age,net_worth;
cin >> name >> age >> net_worth;
v.push_back({name,age,net_worth});
}
sort(v.begin(), v.end(),cmp); //将富豪进行排序
int book[205] = {0}; //用来记录每个年龄段的人数
vector<people> ans;
for(int i = 0; i < N; i++)
{
if(book[v[i].age] <= 100)
{
ans.push_back(v[i]);
book[v[i].age]++;
}
}
for(int i = 1; i <= K; i++)
{
int M,Amin,Amax; //最多输出M个人,年龄区间[Amin,Amax]
cin >> M >> Amin >> Amax;
printf("Case #%d:\n",i);
int cnt = 0; //用来记录已经输出的人数
for(auto it : ans)
{
if(it.age >= Amin && it.age <= Amax && cnt < M)
{
printf("%s %d %d\n",it.name.c_str(),it.age,it.net_worth);
cnt++;
}
}
if(cnt == 0)
{
printf("None\n");
}
}
return 0;
}
腾讯云开发者
