Python模拟餐厅顾客入座与离开：解决餐桌分配与等待超时问题

这个问题可以用模拟的方法来解决，需要跟踪餐桌的使用情况和顾客的等待队列。以下是Python实现方案： ```python import heapq def restaurant_simulation(M, D, customers): # 可用餐桌堆（存储释放时间） available_tables = list(range(1, M+1)) heapq.heapify(available_tables) # 正在使用的餐桌堆（存储（释放时间，桌号）） occupied_tables = [] # 等待队列（存储（到达时间+最大等待时间，到达时间，顾客编号）） waiting_queue = [] results = [] for idx, (arrival_time, max_wait) in enumerate(customers, 1): # 检查是否有餐桌释放 while occupied_tables and occupied_tables[0][0] <= arrival_time: release_time, table = heapq.heappop(occupied_tables) heapq.heappush(available_tables, table) # 处理等待队列中的顾客（按最早能等待到的时间） while waiting_queue and available_tables: max_wait_time, customer_arrival, customer_idx = heapq.heappop(waiting_queue) if customer_arrival + max_wait_time >= arrival_time: table = heapq.heappop(available_tables) release_time = arrival_time + D heapq.heappush(occupied_tables, (release_time, table)) results.append(f"顾客{customer_idx} 入座时间:{arrival_time} 离开时间:{release_time}") else: results.append(f"顾客{customer_idx} 未入座") # 处理当前顾客 if available_tables: table = heapq.heappop(available_tables) release_time = arrival_time + D heapq.heappush(occupied_tables, (release_time, table)) results.append(f"顾客{idx} 入座时间:{arrival_time} 离开时间:{release_time}") else: heapq.heappush(waiting_queue, (arrival_time + max_wait, arrival_time, idx)) # 处理剩余等待队列中的顾客 while waiting_queue: max_wait_time, customer_arrival, customer_idx = heapq.heappop(waiting_queue) results.append(f"顾客{customer_idx} 未入座") return results # 读取输入 M, D = map(int, input().split()) customers = [] while True: try: arrival, max_wait = map(int, input().split()) customers.append((arrival, max_wait)) except: break # 运行模拟并输出结果 results = restaurant_simulation(M, D, customers) for res in results: print(res) ``` 代码逻辑说明： 1. 使用两个堆来管理餐桌：`available_tables`存储可用餐桌编号，`occupied_tables`存储正在使用的餐桌及其释放时间 2. 使用一个堆`waiting_queue`来管理等待的顾客，按最早可能放弃等待的时间排序 3. 对每个到达的顾客，先检查是否有餐桌可以释放 4. 检查等待队列中是否有顾客可以被安排 5. 尝试安排当前顾客，如果不能安排则加入等待队列 6. 最后处理等待队列中剩余的顾客 三条额外需要注意的逻辑点： 1. 处理等待队列时要注意判断顾客是否已经超时（当前时间 > 到达时间+最大等待时间） 2. 餐桌释放时间是基于入座时间计算的，不是基于到达时间 3. 等待队列的处理必须在尝试安排当前顾客之前，以确保先到先服务的原则 ######[AI写代码神器 | 779点数解答 | 2025-03-28 15:50:35]