题目描述

引入最晚完成时间，计算最晚开始时间的核心思想是：一个任务的最晚完成时间取决于依赖于它的任务的最早开始时间，如果没有任务依赖于它，则最晚完成时间就是n。

Python代码

import sys


read_line = sys.stdin.readline

n, m = map(int, read_line().split())

rely = [0]*(m+1)
rely[1:] = list(map(int, read_line().split()))

time_cost = [0]*(m+1)
time_cost[1:] = list(map(int, read_line().split()))

earliest_start_time = [0]*(m+1)
latest_start_time = [0]*(m+1)
latest_finish_time = [0]*(m+1)

# 计算最早开始时间，从前往后算，因为第一个是已知的
for i in range(1, m+1):
    if rely[i] == 0:
        earliest_start_time[i] = 1
    else:
        earliest_start_time[i] = earliest_start_time[rely[i]] + time_cost[rely[i]]

print(*earliest_start_time[1:])

# 检查是否能在n天内完成所有训练
max_finish_time = 0
for i in range(1, m+1):
    max_finish_time = max(max_finish_time, earliest_start_time[i] + time_cost[i] - 1)

if max_finish_time > n:
    exit()

# 计算最晚完成时间，从后向前计算，最后一个已知
for i in reversed(range(1, m+1)):
    if i == m:
        latest_finish_time[m] = n
    else:
        # 计算i以后依赖于i的科目，可能有多个
        dependent_tasks = [j for j in range(i+1, m+1) if rely[j] == i]
        if dependent_tasks:
            # 由依赖i的科目的最早开始时间计算i的最晚完成时间，依赖i的科目的最早开始时间=其最晚完成时间(已算出)-训练时间
            latest_finish_time[i] = min(latest_finish_time[j] - time_cost[j] for j in dependent_tasks)
        else:
            # 没有依赖于i的科目，则其最晚完成时间为n(最后一天)
            latest_finish_time[i] = n

# 由最晚完成时间计算出最晚开始时间
for i in range(1, m+1):
    latest_start_time[i] = latest_finish_time[i] - time_cost[i] + 1

print(*latest_start_time[1:])