大四的萌新辣！

PTA-1028-人口普查

Posted on In Valine:

题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805293282607104

数据范围:

$0 <= N <= 10^5$

样例:

Input:

1
2
3
4
5
6
5
John 2001/05/12
Tom 1814/09/06
Ann 2121/01/30
James 1814/09/05
Steve 1967/11/20

Output:

1
3 Tom John

题目做法

这个题给的输入是比较复杂的，我们在判断是否是一个合理的序列的时候，如果是按照年月日的格式依次判断的话，显然是比较复杂的。

我们采用结构体来存储这个生日：

例如：

1
2
3
4
5
6
7
8
9
typedef struct node
{
    string s;
    int year;
    int month;
    int day;
    /* data*/
}Node;
Node a[maxn];//来存储信息

我们写判断是否是一个合法生日的时候，就要写一下语句：

1
if(a[i].year > 1814 || (a[i].year == 1814 && a[i].month > 9) || (a[i].year == 1814 && a[i].month = 9 && a[i].day > 6) ||a[i].year < 2014 || (a[i].year == 2014 && a[i].month < 9) || (a[i].year == 2014 && a[i].month = 9 && a[i].day < 6) )

并且我们在判断谁是最大生日/最小生日的时候，还要按照年月日依次判断，代码量冗余。

我们可以采用$string$的特性来进行比较。

直接把生日定义成一个$string$类型，$string$可以直接比较大小。

并且我们还可以进一步降低空间复杂度，我们不必开一个struct的数组类型，只需要保存当前的信息和现在当前的已经存在的最大/最小的生日名字信息即可。然后采用线性处理，没读入一个，先判断是否是一个合理的生日序列，然后我们更新当前的最大/最小生日即可。

比较过程可以直接采用$string$比较。【详见代码】

！！！坑点！！！

这个题最后题面说明是:

在一行中顺序输出有效生日的个数、最年长人和最年轻人的姓名，其间以空格分隔。

但是并没有给出一个特殊的样例，就是输出0的时候。如果没有有效的，输出0！！！并且后边不需要带空格 直接换行即可。

暗示：最后我们首先输出计数$cnt$, 然后我们再判断$cnt$是否为0，不为0时，输出最大最小。

【我觉得这就是一个傻逼题目的说明问题还有样例问题…..真的浪费时间】

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
* Copyright(c)
* Author : tiketiskte
*/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
#define INF 0x3f3f3f3f

/* const int maxn = 1e5 + 5; */

using namespace std;
int n;

int main()
{
    IOS 
    int cnt = 0;
    cin >> n;
    string minbirth = "2014/09/06", maxbirth = "1814/09/06";
    string minname = "", maxname = "";
    string temp_name = "", temp_birth = "";
    for (int i = 1; i <= n; i++)
    {
        cin >> temp_name >> temp_birth;
        if (temp_birth >= "1814/09/06" && temp_birth <= "2014/09/06")
        {
            cnt++;
            if (temp_birth >= maxbirth)
            {
                maxname = temp_name;
                maxbirth = temp_birth;
            }
            if (temp_birth <= minbirth)
            {
                minname = temp_name;
                minbirth = temp_birth;
            }
        }
    }
    cout << cnt;
    if (cnt != 0)
    {
        cout << " " << minname << " " << maxname << endl;
    }
    //system("pause");
    return 0;
}

总结点

  1. 一般复杂类型可以转换成字符串的问题，可以采用$STL$去解决。
  2. 输入输出一定要保持一致，不要$cout $和 $printf$混合使用[会发生莫名其妙的bug]

参考资料

https://en.cppreference.com/w/cpp/string/basic_string