题目信息

项目	内容
题目编号	L1-043
题目名称	阅览室
分数	20
作者	陈越
单位	浙江大学

题目描述

天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。

注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。

输入格式

输入在第一行给出一个正整数N（≤10），随后给出N天的纪录。每天的纪录由若干次借阅操作组成，每次操作占一行，格式为：

书号（[1, 1000]内的整数） 键值（S或E） 发生时间（hh:mm，其中hh是[0,23]内的整数，mm是[0, 59]内整数）

每一天的纪录保证按时间递增的顺序给出。

输出格式

对每天的纪录，在一行中输出当天的读者借书次数和平均阅读时间（以分钟为单位的精确到个位的整数时间）。

样例

输入样例：

3
1 S 08:10
2 S 08:35
1 E 10:00
2 E 13:16
0 S 17:00
0 S 17:00
3 E 08:10
1 S 08:20
2 S 09:00
1 E 09:20
0 E 17:00

输出样例：

2 196
0 0
1 60

解题思路

问题分析

1. 数据记录：记录每本书的借出时间（状态S）和归还时间（状态E）
2. 无效记录处理：只有S没有E，或只有E没有S的记录需要忽略
3. 时间计算：借阅时间 = 归还时间 - 借出时间，以分钟为单位
4. 统计输出：输出有效借阅次数和平均阅读时间

算法步骤

1. 读取天数N
2. 对每一天：
   • 初始化借书次数count=0，总阅读时间total=0
   • 创建一个哈希表记录每本书的借出时间
   • 循环读取记录直到书号为0
   • 如果是借书(S)，记录借出时间
   • 如果是还书(E)且该书有借出记录，计算阅读时间并更新统计
   • 忽略无效记录（没有对应的借出或还书）
   • 输出借书次数和平均时间（整数分钟）

时间复杂度

• 时间复杂度：O(N)，其中N为记录总数
• 空间复杂度：O(K)，其中K为同时借出的最大书籍数量（最多1000本书）

代码实现

Java实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        
        for (int day = 0; day < N; day++) {
            Map<Integer, Integer> borrowTime = new HashMap<>(); // 书号 -> 借出时间(分钟)
            int count = 0; // 有效借阅次数
            int totalTime = 0; // 总阅读时间(分钟)
            
            String line;
            while (!(line = br.readLine()).startsWith("0")) {
                String[] parts = line.split(" ");
                int bookId = Integer.parseInt(parts[0]);
                char status = parts[1].charAt(0);
                String[] timeParts = parts[2].split(":");
                int time = Integer.parseInt(timeParts[0]) * 60 + Integer.parseInt(timeParts[1]);
                
                if (status == 'S') {
                    // 借书：记录借出时间
                    borrowTime.put(bookId, time);
                } else if (status == 'E') {
                    // 还书：检查是否有对应的借出记录
                    if (borrowTime.containsKey(bookId)) {
                        int borrowStart = borrowTime.get(bookId);
                        totalTime += (time - borrowStart);
                        count++;
                        borrowTime.remove(bookId);
                    }
                }
            }
            
            // 处理最后一行 0 xxx（这一天结束）
            // 输出结果：借书次数和平均阅读时间
            if (count == 0) {
                System.out.println("0 0");
            } else {
                System.out.println(count + " " + (totalTime / count));
            }
        }
    }
}

Python实现

def time_to_minutes(t):
    h, m = map(int, t.split(':'))
    return h * 60 + m

def main():
    n = int(input().strip())
    
    for _ in range(n):
        borrow_time = {}  # 书号 -> 借出时间(分钟)
        count = 0  # 有效借阅次数
        total_time = 0  # 总阅读时间(分钟)
        
        while True:
            parts = input().split()
            book_id = int(parts[0])
            
            if book_id == 0:
                break
            
            status = parts[1]
            time = time_to_minutes(parts[2])
            
            if status == 'S':
                # 借书：记录借出时间
                borrow_time[book_id] = time
            elif status == 'E':
                # 还书：检查是否有对应的借出记录
                if book_id in borrow_time:
                    total_time += (time - borrow_time[book_id])
                    count += 1
                    del borrow_time[book_id]
        
        # 输出结果：借书次数和平均阅读时间
        if count == 0:
            print("0 0")
        else:
            print(f"{count} {total_time // count}")

if __name__ == "__main__":
    main()

运行验证

样例输入

3
1 S 08:10
2 S 08:35
1 E 10:00
2 E 13:16
0 S 17:00
0 S 17:00
3 E 08:10
1 S 08:20
2 S 09:00
1 E 09:20
0 E 17:00

样例输出

2 196
0 0
1 60

输出解释：

• 第一天：2次有效借阅，平均阅读时间196分钟
• 第二天：0次有效借阅（只有还书没有借书记录）
• 第三天：1次有效借阅，平均阅读时间60分钟

复杂度分析

指标	复杂度	说明
时间复杂度	O(N)	只需遍历所有记录一次
空间复杂度	O(K)	K为同时借出的最大书籍数量（≤1000）

总结

本题是一道经典的哈希表应用题，主要考察：

1. 字符串处理和时间计算
2. 哈希表的使用（记录借出时间）
3. 无效记录的处理
4. 平均值的计算

关键点是用哈希表维护每本书的借出时间，遇到还书记录时查找对应的借出时间即可计算出阅读时长。