概述
原题:https://pintia.cn/problem-sets/994805260223102976/problems/994805293282607104
某城镇进行人口普查,得到了全体居民的生日。现请你写个程序,找出镇上最年长和最年轻的人。
这里确保每个输入的日期都是合法的,但不一定是合理的——假设已知镇上没有超过 200 岁的老人,而今天是 2014 年 9 月 6 日,所以超过 200 岁的生日和未出生的生日都是不合理的,应该被过滤掉。
输入格式:
输入在第一行给出正整数 N,取值在(0,
1
0
5
10^{5}
105];随后 N 行,每行给出 1 个人的姓名(由不超过 5 个英文字母组成的字符串)、以及按 yyyy/mm/dd
(即年/月/日)格式给出的生日。题目保证最年长和最年轻的人没有并列。
输出格式:
在一行中顺序输出有效生日的个数、最年长人和最年轻人的姓名,其间以空格分隔。
输入样例:
5
John 2001/05/12
Tom 1814/09/06
Ann 2121/01/30
James 1814/09/05
Steve 1967/11/20
输出样例:
3 Tom John
题目分析:
将输入的名字和合法的生日用数组存储起来,然后查找数组中的最大和最小元素进行输出。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef struct person {
string name;
string data;
}person;
int isRight(string data1, string today) { // 判断data1是否合法
if (data1 > today) return 0;
else {
int year1 = stoi(data1.substr(0,4));
int year2 = stoi(today.substr(0,4));
string left1 = data1.substr(5, 5);
string left2 = today.substr(5, 5);
if (year2 - year1 > 200) return 0;
else if (year2 - year1 == 200 && left1 < left2) return 0;
else return 1;
}
}
int cmp(person p1, person p2) { // 按照年龄降序
return p1.data < p2.data;
}
int main() {
int N;
cin >> N;
string today = "2014/09/06";
person* p = new person[N];
int num = 0; // 合法的生日数目
while (N--) {
person per;
cin >> per.name;
cin >> per.data;
if (isRight(per.data, today)) p[num++] = per;
}
//sort(p,p+num,cmp);
//printf("%d %s %sn", num, p[0].name, p[num-1].name);发现%s对于string类型并不适用
//cout << num << " " << p[0].name << " " << p[num - 1].name << endl;
int min, max;
min = max = 0;
for (int i = 0; i < num; i++) {
if (p[i].data < p[min].data) min = i;
else if (p[i].data > p[max].data) max = i;
}
cout << num;
if(num) cout << " " << p[min].name << " " << p[max].name << endl;
delete[] p;
system("pause");
}
问题记录:
1.使用排序函数sort()
复杂度在
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn),测试点4会超时;还不如自己遍历一遍数组,复杂度在
O
(
n
)
O(n)
O(n)。
2.c语言中的printf()
的格式字符串%s
只适用于c字符串,即char*
,不适用于C++中的string
类型。
3.当输入的合法日期数为0时,不应该输出人名。
方法改进:
1.观察输出,我们能发现最后的输出结果只有3个,所以我们可以不用声明一个数组来存储所有的生日,只需要用name
和data
来接受输入的名字,日期,然后用cnt
统计合法的生日,同时用maxbirth
和minibirth
记录下最大和最小的生日,这能边输入边记录。
2.判断最大和最小合法日期的时候,不用像方法一那么复杂,因为我们完全可以推断出来,合法日期在"1814/09/06——2014/09/06"
之间。
#include <iostream>
#include <string>
using namespace std;
int main() {
int N;
string maxname, minname, maxbirth, minbirth;
string name, date;
string maxdate = "2014/09/06";
string mindate = "1814/09/06";
maxbirth = mindate; // 当前生日最大的,即最年轻的
minbirth = maxdate; // 当前生日最小的,即最年长的
int cnt = 0; // 合法的生日数
cin >> N;
while (N--) {
cin >> name >> date;
if (date <= maxdate && date >= mindate) {
cnt++;
if (date <= minbirth) {
minname = name;
minbirth = date;
}
if (date >= maxbirth) {
maxname = name;
maxbirth = date;
}
}
}
cout << cnt;
if(cnt) cout << " " << minname << " " << maxname << endl;
system("pause");
}
最后
以上就是动听冬瓜为你收集整理的(PAT Basic)1028.人口普查(元素查找) C++的全部内容,希望文章能够帮你解决(PAT Basic)1028.人口普查(元素查找) C++所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复