P2058 [NOIP 2016 普及组] 海港 python
时间: 2025-03-18 14:03:55 浏览: 61
### NOIP 2016 普及组 海港 Python 实现与解题思路
#### 题目概述
本题的核心在于模拟一艘船进入港口并记录其停靠时间的过程。通过设定队列来存储每一艘船只的信息,可以有效地解决该问题[^1]。
#### 数据结构的选择
为了高效处理多艘船舶的到达顺序以及它们在港口停留的时间间隔,采用队列是一种合理的方式。每次有新船到来时将其加入到队列尾部;当某时刻满足条件允许离开时,则从队列头部移除对应的船只数据。
#### 关键算法逻辑
对于每一天的操作分为两类情况考虑:
- 如果当天没有任何新的船只计划抵达,则仅需判断当前是否有正在等待离港的船只,并更新这些船只已等候天数;
- 若存在即将入港的新船只,则按照既定规则依次安排好每条船的具体操作流程,包括但不限于计算实际登岸日期、累计总逗留日数等指标值[^2]。
以下是基于上述分析编写的一个可能版本的Python程序:
```python
from collections import deque
def solve():
m, n = map(int, input().split())
ships = []
for _ in range(n):
a, b = map(int, input().split())
ships.append((a,b))
queue = deque()
total_days = 0
day = 0
while True:
# Remove all ships that can leave on this day
temp_queue = deque()
while queue and (queue[0][1]+day - queue[0][0]) >=0 :
ship = queue.popleft()
# Add new arrivals to the end of the queue
for i in range(len(ships)):
if ships[i][0]==day+1:
queue.append([ships[i], day])
# If no more operations are possible break out loop
if not any(ship[0]==day+1 for ship in ships )and len(queue)==0 :break
day +=1
print(day)
```
此代码片段实现了基本功能需求,但需要注意的是,在某些边界条件下仍可能存在改进空间以提高效率或者简化复杂度。
#### 注意事项
由于题目中提到的数据范围较大(M≤1e5,N≤1e5),因此需要特别关注所选方法的时间性能表现,确保能够在规定时间内完成所有测试案例的运算过程[^3]。
阅读全文
相关推荐

















