Python：每日一题之观光公交（前缀和）

题目描述

风景迷人的小城 Y 市，拥有 n 个美丽的景点。由于慕名而来的游客越来越多，Y 市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1 号景点，随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻，公交车只能往前开，或在景点处等待。

设共有 m 个游客，每位游客需要乘车 1 次从一个景点到达另一个景点，第 i 位游客在Ti 分钟来到景点 Ai，希望乘车前往景点 Bi（Ai≤Bi）。为了使所有乘客都能顺利到达目的地，公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。

一个乘客的旅行时间，等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车，有时候还要停下来等其他乘客，乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器，每使用一个加速器，可以使其中一个 Di 减 1。对于同一个 Di 可以重复使用加速器，但是必须保证使用后 Di 大于等于 0。

那么 ZZ 该如何安排使用加速器，才能使所有乘客的旅行时间总和最小？

输入描述

第 1 行是 3 个整数 n,m,k，每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 2 行是 n−1 个整数，每两个整数之间用一个空格隔开，第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间，即 Di。

第 3 行至 m+2 行每行 3 个整数 Ti,Ai,Bi，每两个整数之间用一个空格隔开。第 i+2 行表示第 i 位乘客来到出发景点的时刻，出发的景点编号和到达的景点编号。

其中，1≤n≤1000，1≤m≤10^4，0≤k≤10^5，1≤Di≤100，0≤Ti≤10^5

输出描述

输出共一行，包含一个整数，表示最小的总旅行时间。

输入输出样例

示例

输入

输出

说明

对 D2 使用 2 个加速器，从 2 号景点到 3 号景点时间变为 2 分钟。公交车在第 1 分钟从 1 号景点出发，第 2 分钟到达 2 号景点，第 5 分钟从 2 号景点出发，第 7 分钟到达 3 号景点。第 1 个旅客旅行时间 7-0 = 7 分钟。第 2 个旅客旅行时间 2-1 = 1 分钟。第 3 个旅客旅行时间 7-5 = 2 分钟。总时间 7+1+2 = 10 分钟。

思路：

【分析】 —— 在第 i 站使用加速器

1、到达 i+1 站的时间小于以 i+1 站为起点的乘客到达 i+1站最晚的时间；

2、观光车到达 i+1 的时间等于以 i+1 站为起点的乘客到达i+1站最晚的时间；

3、观光车到达 i+1 的时间大于以 i+1 站为起点的乘客到达i+1 站最晚的时间；

参考代码：

前缀和（只能通过80%）

n,m,k = [int(i) for i in input().split()]
d = [int(i) for i in input().split()] #旅途时间
tim = [0 for _ in range(m)]  #到达起始站时刻
st = [0 for _ in range(m)]   #起始车站
nd = [0 for _ in range(m)]   #终点车站
las = [0 for _ in range(n)]  #最后到达的时间
sum = [0 for _ in range(n)]  #i号节点下车人数
go = [0 for _ in range(n)]   #到车时间
rang = [0 for _ in range(n)] #影响范围
tot = 0
for i in range(m):
    tim[i],st[i],nd[i] = [int(i) for i in input().split()]
    st[i], nd[i] = st[i]-1,nd[i]-1
    las[st[i]] = max(las[st[i]],tim[i])
    sum[nd[i]] +=1      
for i in range(1,n):
    sum[i]+=sum[i-1] #前缀和
    go[i]=max(go[i-1],las[i-1])+d[i-1]
for i in range(m):
    tot += go[nd[i]] - tim[i]  #终点-到达时间
while k:
    k-=1
    rang[n-2] = n-1
    for i in range(n-3,-1,-1):
        if go[i+1]<=las[i+1]:
            rang[i] = i + 1
        else:
            rang[i] = rang[i + 1]
    mx = 0
    id = 0
    for i in range(n-1):
        now = sum[rang[i]]-sum[i]
        if mx<now and d[i]:
            mx = now
            id = i
    if mx == 0:
        break
    tot -= mx
    d[id]-= 1
    for i in range(id,rang[id]+1):
        go[i]=max(go[i-1],las[i-1])+d[i-1]
print(tot)