「PAT甲级真题解析」Advanced Level 1006 Sign In and Sign Out

Table of Contents

问题分析

  1. 题目给出一组学生进入机房的进入时间和离开时间, 要求找出最早进入机房开门的人以及最晚离开机房锁门的人. 到这里我们可以看出题目的重点在于查找, 而查找会涉及到数据的存储, 如果存储数据以及在储存的数据中进行查找是我们要考虑的核心。
  2. 我们可以存储所有的进入时间和对应的学生ID, 然后比较出最早的进入时间。但我们在乙级的题目练习中多次提到, 数据存储是为了使用, 在这种情况下, 进入时间在进行一次比较之后就不会再用到了, 所以可以不需要存储全部进入时间, 而是直接存储当前最早进入时间然后不断更新。
  3. 同理, 可以找出最晚离开时间。
  4. 由于要求输出学生ID, 所以要同时存储当前最早进入时间和当前最晚离开时间所对应的学生ID.

完整描述步骤

  1. 获取输入: 学生进出记录数目
  2. 初始化计数器:
    • 当前最早进入时间
    • 当前最早进入时间对应的学生ID
    • 当前最晚离开时间
    • 当前最晚离开时间对应的学生ID
  3. 对每一条学生进出记录:
    • 获取输入: 学生ID, 进入时间, 离开时间
    • 如果该学生进入时间小于当前最早进入时间, 则:
      • 更新"当前最早进入时间"为该学生的进入时间
      • 更新"当前最早进入时间对应的学生ID"为该学生的ID
    • 如果该学生离开时间大于当前最晚离开时间, 则:
      • 更新"当前最晚离开时间"为该学生的离开时间
      • 更新"当前最晚离开时间对应的学生ID"为该学生的ID
  4. 遍历结束, 输出:
    • 当前最早进入时间对应的学生ID
    • 当前最晚离开时间对应的学生ID

伪代码描述

  1. get input: amount
  2. init recorder:
    • min_time = "24:00:00"
    • min_ID = ""
    • max_time = "00:00:00"
    • max_ID = ""
  3. for each record:
    • get record input: ID, in_time, out_time;
    • if in_time < min_time:
      • min_time = in_time;
      • min_ID = ID;
    • if out_time > max_time:
      • max_time = out_time;
      • max_ID = ID;
  4. print(min_ID, max_ID);

完整提交代码

1/*
2# 问题分析
31. 题目给出一组学生进入机房的进入时间和离开时间, 要求找出最早进入机房开门的人以及最晚离开机房锁门的人.
4到这里我们可以看出题目的重点在于查找, 而查找会涉及到数据的存储, 如果存储数据以及在储存的数据中进行查找是我们要考虑的核心。
52. 我们可以存储所有的进入时间和对应的学生ID, 然后比较出最早的进入时间。但我们在乙级的题目练习中多次提到, 数据存储是为了使用,
6在这种情况下, 进入时间在进行一次比较之后就不会再用到了, 所以可以不需要存储全部进入时间, 而是直接存储当前最早进入时间然后不断更新。
73. 同理, 可以找出最晚离开时间。
84. 由于要求输出学生ID, 所以要同时存储当前最早进入时间和当前最晚离开时间所对应的学生ID.
9
10# 完整描述步骤
111. 获取输入: 学生进出记录数目
122. 初始化计数器:
13    - 当前最早进入时间
14    - 当前最早进入时间对应的学生ID
15    - 当前最晚离开时间
16    - 当前最晚离开时间对应的学生ID
173. 对每一条学生进出记录:
18    - 获取输入: 学生ID, 进入时间, 离开时间
19    - 如果该学生进入时间小于当前最早进入时间, 则:
20        - 更新"当前最早进入时间"为该学生的进入时间
21        - 更新"当前最早进入时间对应的学生ID"为该学生的ID
22    - 如果该学生离开时间大于当前最晚离开时间, 则:
23        - 更新"当前最晚离开时间"为该学生的离开时间
24        - 更新"当前最晚离开时间对应的学生ID"为该学生的ID
254. 遍历结束, 输出:
26    - 当前最早进入时间对应的学生ID
27    - 当前最晚离开时间对应的学生ID
28
29# 伪代码描述
301. get input: amount
312. init recorder:
32    - min_time = "24:00:00"
33    - min_ID = ""
34    - max_time = "00:00:00"
35    - max_ID = ""
363. for each record:
37    - get record input: ID, in_time, out_time;
38    - if in_time < min_time:
39        - min_time = in_time;
40        - min_ID = ID;
41    - if out_time > max_time:
42        - max_time = out_time;
43        - max_ID = ID;
444. print(min_ID, max_ID);
45*/
46
47# include<iostream>
48using namespace std;
49
50int main(){
51    int amount;
52    cin >> amount;
53    string ID, in_time, out_time;
54    string max_ID = "";
55    string max_time = "00:00:00"; 
56    string min_ID = "";
57    string min_time = "24:00:00";
58    for (int i = 0; i < amount; i++){
59        cin >> ID >> in_time >> out_time;
60        int res = in_time.compare(min_time);
61        if (res < 0){
62            min_time = in_time;
63            min_ID = ID;
64        }
65        res = out_time.compare(max_time);
66        if (res > 0){
67            max_time = out_time;
68            max_ID = ID;
69        }
70        
71    }
72    
73    cout << min_ID << " " << max_ID;
74    
75    return 0;
76}
Mastodon