观光公交

GitHub跳转原题关系图返回列表

把总旅行时间改写为按下车点加权的到达时刻和，贪心把加速器投给单位收益最大的边，再用饱和事件把逐个加速压成 O(n²) 批量执行。

OJ: roj

题目 ID: 3593

难度:提高

标签:贪心模拟python

创建: 2026-10-02 09:34

更新: 2026-10-10 11:30

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

nn 个景点排成一条链，第 ii 段（景点 i→i+1i \to i+1）行驶需要 DiD_i 分钟。公交第 00 分钟出现在景点 11，只能前进或在景点处等待，并且必须等齐该站所有乘客才发车，即

dep[i]=max⁡(arrive[i], W[i]),W[i]=在景点 i 上车的乘客的最晚到达时刻.\mathrm{dep}[i] = \max\big(\mathrm{arrive}[i],\ W[i]\big),\qquad W[i] = \text{在景点 } i \text{ 上车的乘客的最晚到达时刻}.

mm 位乘客各在 TpT_p 时刻到达景点 ApA_p、要去景点 BpB_p（Ap<BpA_p < B_p），旅行时间 == 公交到达 BpB_p 的时刻 − Tp-\ T_p。有 kk 个氮气加速器，每个可以把某段 DiD_i 减 11（同一段可叠加，但必须保持 Di⩾0D_i \geqslant 0）。求所有乘客旅行时间总和的最小值。

样例（n=3n=3，D=[1,4]D=[1,4]，乘客 (0,1,3),(1,1,2),(5,2,3)(0,1,3),(1,1,2),(5,2,3)，k=2k=2）的时间线如下，用来说明"等齐再发车"和加速器的效果：

时刻 事件 说明
0 公交到达景点 1 站 1 有乘客 1 分钟才到，等到 1 分发车
2 到达景点 2 发车时刻 max⁡(0,1)\max(0,1)，再走 D1=1D_1=1 分钟
5 从景点 2 发车 站 2 有乘客 5 分钟才到，W[2]=5W[2]=5，等到 5 分
7 到达景点 3 对 D2D_2 用了 2 个加速器，4→24 \to 2

于是三位乘客的旅行时间为 7−0=77-0=7、2−1=12-1=1、7−5=27-5=2，总和 1010。若不加速，公交 99 分钟才到景点 3，总和是 9+1+4=149+1+4=14——加速器的全部收益，就在于让某些站的到达时刻提前。

正解

思路

先把目标从"乘客"换成"站点"。 乘客的 TpT_p 与加速器无关，所以最小化总旅行时间等价于最小化 ∑parrive[Bp]\sum_p \mathrm{arrive}[B_p]。按下车点聚合：记 gjg_j 为在景点 jj 下车的乘客数，目标即最小化 ∑jarrive[j]⋅gj\sum_j \mathrm{arrive}[j]\cdot g_j——只要知道哪些站的到达时刻被提前了、提前了多少，答案就出来了。

朴素做法与瓶颈。 最容易想到的贪心是：重复 kk 次，每次把某段 DiD_i 减 11 试算全部乘客的时间减少量，选减少最多的那条边真减。一次试算要模拟整条线路 O(n+m)O(n+m)，总复杂度 O(k(n+m))O(k(n+m))，按 k⩽105k \leqslant 10^5、m⩽104m \leqslant 10^4 约 10910^9 次运算，必然超时。方向没有错（这正是本题的标准贪心），问题在于：相邻两次试算只差 1 分钟，收益表几乎纹丝不动，重算了 kk 遍几乎相同的状态。

关键观察一：提前量沿链条传播，被"等待余量"截断。 记 aja_j 为景点 jj 的到达时刻比原始时间线提前的分钟数。某段 DiD_i 减 11 后 ai+1a_{i+1} 加 11，并尝试向下游传递；站 jj 的发车时刻提前量 =min⁡(aj, cap[j])= \min(a_j,\ \mathrm{cap}[j])，其中 cap[j]=max⁡(arrive0[j]−W[j],0)\mathrm{cap}[j]=\max(\mathrm{arrive}_0[j]-W[j],0) 是该站的等待余量——只要 aj<cap[j]a_j < \mathrm{cap}[j]，发车时刻就跟着提前，传递继续；一旦 aja_j 顶到 cap[j]\mathrm{cap}[j]，等待把提前量吃掉，链条截断。cap\mathrm{cap} 只由原始时间线决定，是常数；cap[j]=0\mathrm{cap}[j]=0 的站（或提前量已用满余量的站）称为饱和站，它自身的到达时刻仍能提前，只是不再向下游放行：

flowchart TD
    A["第 i 段 D_i 减 1"] --> B["站 i+1 到达时刻提前 1"]
    B --> C{"站 j 还有等待余量吗<br/>ahead[j] &lt; cap[j]"}
    C -- 是：发车也提前 1 --> D["提前量继续传给站 j+1"]
    D --> C
    C -- 否：饱和站，等待吃掉提前量 --> E["链条截断<br/>只保留站 j 自身的收益"]

关键观察二：单位收益只由饱和分布决定，O(n)O(n) 求出全部。 给第 ii 段再减 11，提前量从站 i+1i{+}1 出发，止于第一个饱和站（含该站）。所以第 ii 段的单位收益 == 这条链上下车的乘客数：

benefit[i]=∑j=i+1Rigj=prefix[Ri]−prefix[i],\text{benefit}[i] = \sum_{j=i+1}^{R_i} g_j = \text{prefix}[R_i] - \text{prefix}[i],

其中 RiR_i 是从 i+1i{+}1 起最近的饱和站（没有则为 nn），prefix\text{prefix} 是 gg 的前缀和。一次倒序扫描得到"最近饱和站"数组后，n−1n-1 条边的收益全部 O(n)O(n) 算完，选最大者。

关键观察三：批量加速，轮数只与饱和事件有关。 一次给选中的边注入 tt 个加速器，只要途中没有站首次饱和，收益表完全不动，tt 可以一路加到第一个事件为止：

  • 某站首次饱和——全体站最多饱和 n−1n-1 次；
  • 或该段耗尽（Xi=DiX_i=D_i）——最多 n−1n-1 次；
  • 或加速器用完。

每轮必发生其中一种，故总轮数 ⩽2n\leqslant 2n，每轮 O(n)O(n)，总复杂度 O(n2+m)O(n^2+m)，kk 的因子被彻底消掉。这与"逐个加速器、每次重算"产生完全相同的选边序列（批量只在收益恒定的区间内进行），只是把重复计算省掉了。

样例上的执行过程（g2=1g_2=1，g3=2g_3=2，cap[2]=max⁡(2−5,0)=0\mathrm{cap}[2]=\max(2-5,0)=0，cap[3]=9\mathrm{cap}[3]=9）：

轮次 收益链条 边 1 收益 边 2 收益 决策
1 边 1 止于饱和站 2；边 2 链到终点站 3 g2=1g_2=1 g3=2g_3=2 选边 2，批量注入 min⁡(k=2, D2=4, 距饱和 9)=2\min(k=2,\ D_2=4,\ \text{距饱和 }9)=2
2 加速器已用完 — — 停止，输出 14−2×2=1014-2\times 2=10

站 2 一开始就是饱和站（a2=0⩾cap[2]=0a_2=0 \geqslant \mathrm{cap}[2]=0）：边 1 提前只会让公交更早到站 2，反正要等到 5 分——提前量被等待完全吃掉，这正是链条截断机制要表达的含义。

正确性上，目标对每段注入是凹的：链条上的 min⁡\min 截断使边际收益只减不增，且不同段的注入竞争同一批等待余量（互相替代）。在这种结构下，把加速器逐个投给当前单位收益最大的边不会比任何分配差；而批量执行按"首次饱和"截停，与逐个执行严格等价。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INFLL = (1LL<<60);
int n, tourists, k; vector<ll> d, waitv, alightv, capv, prefixv, aheadv, usedv;
vector<int> next_saturated(){ vector<int> sat(n+2,n+1); for(int j=n;j>=2;j--) sat[j]=(aheadv[j]>=capv[j]?j:sat[j+1]); return sat; }
int pick_edge(vector<int> &sat){ int best=0; ll gain=0; for(int i=1;i<(int)d.size();i++){ if(usedv[i]>=d[i]) continue; int stop=sat[i+1]; if(stop>n) stop=n; ll gi=prefixv[stop]-prefixv[i]; if(gi>gain){best=i; gain=gi;} } return best; }
ll batch_limit(int start, ll budget){ ll gate=INFLL,event=INFLL; for(int j=start+1;j<(int)aheadv.size();j++){ if(aheadv[j]>=capv[j]) break; ll room=capv[j]-aheadv[j]; if(room<=gate) event=min(event, room); gate=min(gate, room); } return min(budget,event); }
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); if(!(cin>>n>>tourists>>k)) return 0; d.assign(n,0); for(int i=1;i<n;i++) cin>>d[i]; waitv.assign(n+1,0); alightv.assign(n+1,0); ll total_t=0; for(int i=0;i<tourists;i++){ll t; int a,b; cin>>t>>a>>b; waitv[a]=max(waitv[a],t); alightv[b]++; total_t += t;} vector<ll> arrive(n+1); for(int i=1;i<n;i++) arrive[i+1]=max(arrive[i],waitv[i])+d[i]; capv.assign(n+1,0); for(int i=2;i<=n;i++) capv[i]=max(arrive[i]-waitv[i],0LL); prefixv.assign(n+1,0); for(int j=2;j<=n;j++) prefixv[j]=prefixv[j-1]+alightv[j]; aheadv.assign(n+1,0); usedv.assign(n+1,0); int remain=k; while(remain>0){ vector<int> sat=next_saturated(); int edge=pick_edge(sat); if(edge==0) break; ll budget=min((ll)remain, d[edge]-usedv[edge]); ll step=batch_limit(edge,budget); usedv[edge]+=step; remain-=step; ll delta=step; for(int j=edge+1;j<=n;j++){ ll room=capv[j]-aheadv[j]; aheadv[j]+=delta; delta=min(delta, room); if(delta<=0) break; } }
    ll base=0,saved=0; for(int j=2;j<=n;j++){ base += arrive[j]*alightv[j]; saved += aheadv[j]*alightv[j]; } cout << base-total_t-saved << '\n'; return 0; }
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:34
# update_at: 2026-10-02 09:34

import sys

INF = 10**18  # "不会发生"的事件时刻：链条上没有任何饱和站点


def next_saturated(ahead: list[int], cap: list[int]) -> list[int]:
    """sat[j] = ≥j 的最近饱和景点编号，n+1 表示 j 往后一路畅通。"""
    n = len(ahead) - 1
    sat = [n + 1] * (n + 2)
    for j in range(n, 1, -1):
        sat[j] = j if ahead[j] >= cap[j] else sat[j + 1]
    return sat


def pick_edge(sat: list[int], prefix: list[int], d: list[int], used: list[int]) -> int:
    """在还有加速名额的边里选单位收益最大的一条：收益 = 链条下游的下车人数；无正收益返回 0。"""
    best, gain = 0, 0
    for i in range(1, len(d)):
        if used[i] >= d[i]:
            continue                     # 这段已减到 0，不能再加速
        stop = sat[i + 1]                # 收益链条的终点：最近的饱和景点
        if stop >= len(prefix):          # 没有饱和站点，链到终点站
            stop = len(prefix) - 1
        gain_i = prefix[stop] - prefix[i]  # 环节 [i+1, stop] 的下车人数
        if gain_i > gain:
            best, gain = i, gain_i
    return best


def batch_limit(ahead: list[int], cap: list[int], start: int, budget: int) -> int:
    """start 段一次能批量加多少个加速器：到"第一次饱和截断收益"为止，或用完 budget。"""
    gate = INF   # 链条上游各站还能放行的提前量下限
    event = INF  # 第一次让某站恰好饱和所需的提前量
    for j in range(start + 1, len(ahead)):
        if ahead[j] >= cap[j]:
            break                        # 已饱和：本站之后链条已断，不再有新事件
        room = cap[j] - ahead[j]         # 本站还能吃下的提前量
        if room <= gate:
            event = min(event, room)     # 加满 room 本站就饱和
        gate = min(gate, room)
    return min(budget, event)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, tourists, k = next(data), next(data), next(data)
    d = [0] + [next(data) for _ in range(n - 1)]  # d[i]：景点 i → i+1 的原始车程

    wait = [0] * (n + 1)     # wait[i]：在景点 i 上车的最晚到达时刻（车要等齐）
    alight = [0] * (n + 1)   # alight[j]：在景点 j 下车的乘客数
    total_t = 0
    for _ in range(tourists):
        t, a, b = next(data), next(data), next(data)
        wait[a] = max(wait[a], t)
        alight[b] += 1
        total_t += t

    # 不加速时的到达时刻：到站后等到最晚乘客才发车
    arrive0 = [0] * (n + 1)
    for i in range(1, n):
        arrive0[i + 1] = max(arrive0[i], wait[i]) + d[i]

    # cap[i] = 等待余量：到达时刻提前量不超过它时发车跟着提前，超过的部分被等待吃掉
    cap = [0] * (n + 1)
    for i in range(2, n + 1):
        cap[i] = max(arrive0[i] - wait[i], 0)

    prefix = [0] * (n + 1)  # prefix[x] = Σ_{j≤x} alight[j]
    for j in range(2, n + 1):
        prefix[j] = prefix[j - 1] + alight[j]

    ahead = [0] * (n + 1)   # ahead[i]：第 i 段已累计提前的分钟数
    used = [0] * (n + 1)    # used[i]：第 i 段已用掉的加速器数
    remain = k

    while remain > 0:
        edge = pick_edge(next_saturated(ahead, cap), prefix, d, used)
        if edge == 0:
            break                              # 没有正收益的边，再加速也无用
        budget = min(remain, d[edge] - used[edge])
        step = batch_limit(ahead, cap, edge, budget)
        used[edge] += step
        remain -= step

        # 提前量沿链条向下游传播：每过一站最多被该站的等待余量吃掉
        delta = step
        for j in range(edge + 1, n + 1):
            room = cap[j] - ahead[j]
            ahead[j] += delta
            delta = min(delta, room)
            if delta <= 0:
                break

    base = sum(arrive0[j] * alight[j] for j in range(2, n + 1)) - total_t
    saved = sum(ahead[j] * alight[j] for j in range(2, n + 1))
    print(base - saved)


if __name__ == "__main__":
    solve()

复杂度

  • 时间复杂度：O(n2+m)O(n^2+m)。预处理 O(n+m)O(n+m)；主循环每轮 O(n)O(n)，每轮至少触发一次"新饱和 / 边耗尽"，总轮数 ⩽2n\leqslant 2n。相比朴素的 O(k(n+m))≈109O(k(n+m))\approx 10^9，消掉了 k⩽105k\leqslant10^5 的因子。
  • 空间复杂度：O(n)O(n)，约十个长度为 nn 的数组，n⩽1000n\leqslant1000 时仅几十 KB。
  • 实测：20 组真实数据全部一致，单点 0.016–0.043 s、峰值内存 ⩽\leqslant 17 MB，相对 1000 ms / 32 MB 的限制十分宽裕。

总结

这道题的三层转化是关键：总旅行时间 →\to 按下车点加权的到达时刻和 →\to 每站的"提前量" aja_j →\to 被等待余量 cap[j]\mathrm{cap}[j] 逐站截断的传播链条。收益结构一旦看清，贪心就是"每次把加速器投给链条上下车人数最多的那条边"；而"收益表只在站点首次饱和时才改变"这一事件性质，把 O(k(n+m))O(k(n+m)) 的逐个执行压成 O(n2+m)O(n^2+m) 的批量执行。

实现时注意三点：截断要用注入前的余量 cap[j] - ahead[j] 计算；饱和站自身的到达时刻仍算收益，链条"止于且包含"第一个饱和站；加速器耗尽或所有边收益为 0 时立即退出，避免无意义的空转。实测 20 组真实数据全部一致，样例输出 1010。