[PAT B1028]人口普查
题目描述
1028 人口普查 （20 分）某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。
这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过 200 岁的老人，而今天是 2014 年 9 月 6 日，所以超过 200 岁的生日和未出生的生日都是不合理的，应该被过滤掉。
输入格式
输入在第一行给出正整数 N，取值在(0,10?5??]；随后 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
解析
- 这道题目其实使用的算法没什么，就是特别繁琐，（以至于我觉得这题放在甲级真题比较好。。。）最最最最最麻烦的就是对于日期的处理，我在前几篇博客中提到说对于查找这种数据，最好在输入元素的过程中解决掉问题，这样是最简单的，代码也很简洁，但是这道题目没有办法，因为比较出生年月日实在是太繁琐了，以至于我第一次写了差不多70行代码后放弃了，而重新使用了结构体。
- 这个问题很复杂的就是，关于日期的处理；关于怎么识别出非法的出生日期；以及关于如何求出合法的日期中最小和最大的日期
- 我使用了结构体存放数据，并使用了一个vector来存放N个人，然后重写了cmp函数对年月日进行排序，至于要找到第一个合法的出生日期和最后一个合法的出生日期，那就需要写比较大小函数，那样太麻烦。于是我使用了两个结构体，一个存放的是合法日期的前一天，一个存放的是合法日期的后一天，把他们加入到vector中，我们就可以找到合法的数据的范围了
代码很复杂，接下来会介绍柳神的代码，属于参考，只是希望大家能利用更好的算法解决问题，侵删
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct person //结构体的构成
{
string name;int born[3]; //依次存放年月日
};
bool cmp(person p1, person p2) //写cmp函数，按升序排列
{
if (p1.born[0] != p2.born[0]) return p1.born[0] < p2.born[0];else{
if (p1.born[1] != p2.born[1]) return p1.born[1] < p2.born[1];else return p1.born[2] < p2.born[2];}
}
int main()
{
int N, count = 0;int left, right; //存放合法范围的左边界和右边界vector<person> ps;cin >> N;person p_young = {
"",1814,9,5 }, p_old = {
"",2014,9,7 }; //两个边界数据ps.push_back(p_young);ps.push_back(p_old);while (N--) //输入数据{
person p;cin >> p.name;scanf_s("%d/%d/%d", &p.born[0], &p.born[1], &p.born[2]);ps.push_back(p);}sort(ps.begin(), ps.end(), cmp);for (int i = 0; i < ps.size(); i++){
if (ps[i].born[0] == p_young.born[0] && ps[i].born[1] == p_young.born[1] && ps[i].born[2] == p_young.born[2]){
left = i;while (ps[left].born[0] == p_young.born[0] && ps[left].born[1] == p_young.born[1] && ps[left].born[2] == p_young.born[2]) left++; //找到合法数据的最左边界}if (ps[i].born[0] == p_old.born[0] && ps[i].born[1] == p_old.born[1] && ps[i].born[2] == p_old.born[2]){
right = i;while (ps[right].born[0] == p_old.born[0] && ps[right].born[1] == p_old.born[1] && ps[right].born[2] == p_old.born[2]) right--; //找到合法数据的最右边界}}if (left - right == 1) cout << "0"; //！！！注意，有可能没有合法数据，需要输出0else cout << (right - left + 1) << " " << ps[left].name << " " << ps[right].name;return 0;
}- 写完之后觉得，太复杂了，于是我翻阅了柳神的代码，令我吃惊的是，柳神还是没有使用结构体来解决这个问题（这里推荐一下柳神的代码，每次看柳神的题解都能让人眼前一亮，全是惊喜），柳神直接使用了字符串maxbirth和minbirth存放出生日期，直接使用字符串比较解决问题，即判断是否在合法日期之内的判断条件是
if (birth >= "1814/09/06" && birth <= "2014/09/06") - 要证明的话就是要先了解字符串的比较，字符串的比较使用的方法就是首先比较第一个字母，如果相等再比较第二个，依次类推，如果都相等，就比较长度。因为格式严格规定为yyyy/mm/dd，那么就不存在干扰数据导致题目出错了，满足第一个条件，它的年份如果完全一致的话就会接着比较月份、日期，这样利用字符串的比较来实现这种数据的比较，我只能说真是神来之笔。
- 下面放柳神的代码，大家可以顺着思路先自己做一遍（侵删）：
#include <iostream>
using namespace std;
int main() {
int n, cnt = 0;
cin >> n;
string name, birth, maxname, minname, maxbirth = "1814/09/06", minbirth =
"2014/09/06";
for (int i = 0; i < n; i++) {
cin >> name >> birth;
if (birth >= "1814/09/06" && birth <= "2014/09/06") {
cnt++;
if (birth >= maxbirth) {
maxbirth = birth;
maxname = name;
}
if (birth <= minbirth) {
minbirth = birth;
minname = name;
}
}
}
cout << cnt;
if (cnt != 0) cout << " " << minname << " " << maxname;
return 0;
}