USACO 2020年12月铜组Q3 Stuck in a Rut 碰撞逻辑错误求解

原代码核心问题 #

• 没有按照碰撞发生的时间顺序处理事件：更早发生的碰撞会直接阻挡奶牛，导致后续原本可能发生的碰撞失效，原代码随机遍历奶牛对，会出现先处理晚碰撞、错误标记奶牛停止的问题
• 没有验证阻挡方是否能存活到碰撞发生的时间：若阻挡的奶牛在碰撞发生前就已经被其他奶牛挡住，本次碰撞不会发生
• 没有记录奶牛实际的停止时间，无法判断某次碰撞是否在奶牛已经停止后才发生

修复思路 #

1. 遍历所有东向（E）和北向（N）的奶牛对，筛选出所有可能发生的碰撞事件，计算碰撞时间、被阻挡奶牛、阻挡方奶牛以及阻挡方到达交汇点的时间
2. 将所有碰撞事件按发生时间从小到大排序，优先处理更早的碰撞
3. 处理事件时检查两个条件：
   • 被阻挡的奶牛尚未停止移动
   • 阻挡方奶牛要么没有停止，要么停止时间大于等于它到达交汇点的时间（说明阻挡方能顺利走到交汇点吃掉草）
     两个条件都满足时，标记被阻挡奶牛的停止时间

修复后代码 #

class Cow:
    def __init__(self, idx, x, y):
        self.idx = idx
        self.x = x
        self.y = y
        self.stop_time = float('inf')  # 初始为无穷大，表示不会停止

n = int(input())
cows = []
east = []
north = []
for i in range(n):
    dir, x, y = input().split()
    x = int(x)
    y = int(y)
    cow = Cow(i, x, y)
    cows.append(cow)
    if dir == 'E':
        east.append(cow)
    else:
        north.append(cow)

events = []
# 遍历所有E和N的组合，生成碰撞事件
for e in east:
    for n_cow in north:
        # 交汇点是(n_cow.x, e.y)，首先得满足E能到x=n_cow.x，N能到y=e.y
        if e.x < n_cow.x and n_cow.y < e.y:
            # E到交汇点的时间
            t_e = n_cow.x - e.x
            # N到交汇点的时间
            t_n = e.y - n_cow.y
            if t_e < t_n:
                # E先到，N会在t_n时间被挡，阻挡方是E
                events.append((t_n, n_cow, e, t_e))
            elif t_n < t_e:
                # N先到，E会在t_e时间被挡，阻挡方是N
                events.append((t_e, e, n_cow, t_n))

# 按碰撞时间从小到大排序
events.sort()

for event in events:
    t_block, blocked_cow, block_cow, t_block_arrive = event
    # 被挡的已经被挡了，跳过
    if blocked_cow.stop_time != float('inf'):
        continue
    # 阻挡方在到达交汇点前就被挡了，本次碰撞不生效
    if block_cow.stop_time <= t_block_arrive:
        continue
    # 标记被挡的时间
    blocked_cow.stop_time = t_block

# 按输入顺序输出
for cow in cows:
    if cow.stop_time == float('inf'):
        print("Infinity")
    else:
        print(cow.stop_time)

该代码运行题目给出的样例输入可得到完全匹配的样例输出。

内容的提问来源于stack exchange，提问作者CoderTang