The 2025 ICPC 德国 German Collegiate Programming Contest——B. Bustling Busride（可以思考你想出来的中间变量和原答案之间有什么关系） · znzryb
## 题目大意
**题目大意**
巴瑟普顿大学（Bithampton）有一条通往市中心的公交线路，沿途设有多个停靠站。当前有 $n$ 名学生在大学（第 0 站）排队等车，每位学生都有一个确定的目的地站点。
公交车按固定时间间隔发车，第一辆车在时刻 0 到达，之后每隔 $r$ 秒有一辆车到达。每辆公交车的容量无限，司机可以决定让队列最前端的多少人乘坐当前这辆车。
为了应对拥挤，公交公司规定了特殊的上下车规则：
如果车上有任何一名乘客的目的地是当前站点，则**车上所有乘客**都必须下车。未到达目的地的乘客随后需要重新上车继续行程。
时间计算规则如下：
1. **上下车耗时**：每有一名乘客上车或下车，公交车都需要等待 $w$ 秒。
- 在起点上车：耗时为（上车人数 $\times w$）。
- 在途中站点下车：耗时为（车上总人数 $\times w$）。
- 在途中站点重新上车：耗时为（继续行程人数 $\times w$）。
1. **行驶耗时**：站点之间的行驶时间给定。
你的目标是为每辆公交车分配乘客（即决定每次从队首取多少人上车），使得所有学生到达各自目的地的耗时中的**最大值最小**。
**输入格式**
第一行包含四个整数 $n, b, r, w$ ($1 \le n, b \le 10^5, 1 \le r, w \le 10^6$)，分别表示乘客总数、站点总数、公交车发车间隔、上下车每人次的耗时。
第二行包含 $b$ 个整数 $d_i$ ($1 \le d_i, \sum d_i \le 10^6$)，表示从第 $i-1$ 站行驶到第 $i$ 站所需的时间。
第三行包含 $n$ 个整数 $t_i$ ($1 \le t_i \le b$)，按队列顺序给出第 $i$ 个人的目的地站点编号。
**输出格式**
输出一个整数，表示让所有人都到达目的地所需的最小的最大时间。
**样例数据**
```
Input
3 3 20 1
2 2 2
2 3 1
Output
18
Input
4 2 1 10
3 2
1 2 2 1
Output
27
Input
5 3 3 3
2 2 1
3 3 2 1 1
Output
17
```
**样例解释**
在第一个样例中，最优策略是让所有 3 个人都乘坐第一辆车（时刻 0 到达）。
1. **起点（大学）**：3 人上车，耗时 $3 \times 1 = 3$ 秒。此时车上人员目的地为 $\{2, 3, 1\}$。
1. **行驶至站点 1**：耗时 2 秒。到达时刻 $3+2=5$。
1. **站点 1**：此时有一人（目的地为 1）需要下车。规则要求所有人下车。
- 3 人下车，耗时 $3 \times 1 = 3$ 秒。时刻 $5+3=8$。该乘客到达。
- 剩余 2 人（目的地 2, 3）重新上车，耗时 $2 \times 1 = 2$ 秒。时刻 $8+2=10$。
1. **行驶至站点 2**：耗时 2 秒。到达时刻 $10+2=12$。
1. **站点 2**：此时有一人（目的地为 2）需要下车。
- 2 人下车，耗时 $2 \times 1 = 2$ 秒。时刻 $12+2=14$。该乘客到达。
- 剩余 1 人（目的地 3）重新上车，耗时 $1 \times 1 = 1$ 秒。时刻 $14+1=15$。
1. **行驶至站点 3**：耗时 2 秒。到达时刻 $15+2=17$。
1. **站点 3**：最后一人下车。
- 1 人下车，耗时 $1 \times 1 = 1$ 秒。时刻 $17+1=18$。该乘客到达。
所有乘客到达时间的最大值为 18。
## 思路讲解
::: AI 提示
你的直觉没问题，"每班车运行时间"确实是这题的核心量。最自然的用法是这样的：
**二分答案** $T$**（所有人最晚到达时间），每班车自然获得各自的运行时间预算。**
具体来说，第 $j$ 班车（从 0 开始编号）在时刻 $j \cdot r$ 发车，那么它的运行时间预算就是 $T - j \cdot r$。这不是一个统一的上限，而是递减的——越晚发的车预算越少。这比统一上限更优，因为第一班车有更多余裕去多带人。
判定函数：贪心地从队列头部往后取，每班车在自己的预算内尽量多塞人。如果全部 $n$ 人都能被分配完，则 $T$ 可行。
关键是怎么快速算一辆车的运行时间。有一个很干净的公式：运行时间。
$\text{prefD}[s_{max}] + 2w \cdot \sum_{i} \text{rank}(t_i)$
其中：
- $s_{\max}$ 是这辆车上所有乘客目的地的最大值
- $\text{rank}(t_i)$ = 这辆车上，目的地 $\le t_i$ 的**不同目的地个数**（包括 $t_i$ 自身）
直觉解释：每个乘客贡献的 $w$ 次数 = 上车 1 次 + 最终下车 1 次 + 在每个比自己早的中间站被迫下车再上车各 1 次，合计 $2 \times \text{rank}$。
用样例 1 验证：3 人去站 $\{2,3,1\}$，$w=1$，$d=[2,2,2]$。
- 不同目的地 $\{1,2,3\}$，$\text{rank}(2)=2, \text{rank}(3)=3, \text{rank}(1)=1$
- 运行时间 $= 6 + 2 \times 1 \times (2+3+1) = 6 + 12 = 18$ ✓
**增量维护**：往当前车里逐个添加乘客时，用两个树状数组（BIT，下标为站点 $1 \sim b$）：
- BIT1 记录哪些站是当前车上的不同目的地（查前缀和得 rank）
- BIT2 记录每个站有多少乘客（查后缀和得"目的地比当前人大的已有乘客数"，用于新增不同目的地时调整 sum\_ranks）
添加一个目的地为 $t$ 的乘客：
- 若 $t$ 已出现过：`sum_ranks += BIT1.query(t)`，完事
- 若 $t$ 是新目的地：先 `sum_ranks += (已有乘客数 - BIT2.query(t))`（已有乘客中目的地 $> t$ 的，rank 各 +1），再 `sum_ranks += BIT1.query(t) + 1`（新乘客自身的 rank），然后更新 BIT1
每次操作 $O(\log b)$，换车时只清除用过的位置。总判定复杂度 $O(n \log b)$，外层二分答案 $O(\log T_{\max})$，整体 $O(n \log b \cdot \log T_{\max})$，大约 $6 \times 10^7$，5 秒时限非常宽裕。
:::
这个 Opus 4.6给出的提示非常好，就是二分还是二分那个答案，答案就是最大的到达时间。但是，然后我们给出了一个中间量，我们给出了一个中间量，这个中间量是什么呢？这个中间量就是**一辆车可以最长运行多长时间**。不过我们其实没有意识到一件事情啊，就是其实一辆车**可以最长运行多长时间**，可以**非常自然的使用这个答案推出来**。
下面这个代码，核心的这个代码中的注释，我认为已经非常详细了。我就不多说了，这道题目核心就是这个 check 函数嘛，这个 check 函数的核心已经在上面讲过了。说白了二分答案，首先需要想的就是是不是一定要二分这个答案？可不可以二分其他的东西？当然了，这道题目当然了，就是如果发现你找了一个东西，但是你发现它好像没那么容易二分，或者你觉得好像有点奇怪。这个时候就需要想这个东西和答案之间是不是有什么关系。比如说我我们想到的这个参数，**班次的最长运行时间**，那么我们发现其实是**和这个答案是有关系**的。或者你可以换一种角度，就这个答案往往无法指导我们直接进行选择，进行抉择。我们需要**对答案进行一些转化**，以便指导我们，**进行选择**与抉择。
```cpp
auto check=[&](ll b_ans) -> bool {
ll idx=1;
// 第几班次
for (ll run=1;run<=N;++run) {
if (idx>N) {
return true;
}
ll st_run=(run-1)*R_wait;
// 该班次最大运行时间
ll mx_run=b_ans-st_run;
if (mx_run<0 && idx<=N) {
return false;
}
ll cur=0;
ordered_set pbds;
// 我们下面的注释里面详细说了为什么不需要算他的零站上去的那个情况，实际上已经被我们的二乘 pre 乘以 tim 给覆盖了。
// pbds.insert(0);
ordered_pair_set multi_pbds;
ll mx_terminal=0;
while (true) {
if (idx>N) {
return true;
}
// 我们目前是需要算，加上这个 IDX 对于我们目前运行时间的增量。
// 这个增量分为两部分，一个是我们带来的增量，就是我们给等待时间所有的带来的增量。
// 所有的站，所有在我们之前的站的等待时间（包括我们自己这一站），都需要加上我们下车的这个时间。
ll terminal=t_ls[idx];
mx_terminal=max(mx_terminal,terminal);
ll pre=pbds.order_of_key(terminal)+1;
// 你可能会说这个零站点到底是在哪里被加了呢？
// 那么其实就是在这个 add，这个2× pre 乘以 W tim 里面，就我们就加了这个零站点。
// 实际上，PRE 是包含 TERMINAL 这个站的，但是这个人在 TERMINAL 站，他下来以后就不会上去了。
// 所以二乘以 PRE，那么实际上包含他在零站上去的这个情况。他在零站上去的情况正好弥补了
// 我们多算的他在 TERMINAL 站下来的这个情况，
ll add=2*pre*W_tim;
if (pbds.find(terminal)==pbds.end()) {
// 如果这个 terminal 之前没有出现过，那么所有在其之后的也需要贡献对这个 terminal 进行贡献。
// 所以在其之后的原来就在他之后的点需要对这个 terminal 进行贡献。
// 这里我们使用一个pair 实现的 multi pbds 实现。
ll suf=SZ(multi_pbds)-multi_pbds.order_of_key({terminal,INF});
// 所有在其后面的点都需要在该站下去以后再上来，所以说是 2*suf*W_tim
add+=2*suf*W_tim;
}
if (cur+add+pre_sum[mx_terminal]>mx_run) {
break;
}
cur+=add;
pbds.insert(terminal);
multi_pbds.insert({terminal,idx});
++idx;
}
}
// 如果说大于 N 那么就说明所有的乘客都被处理完了。
return idx>N;
};
```
## AC代码
::: 自定义结构体与 pair 的速度差异
不住了，QOJ 的机器出现了这个时间的倒转，应该是 QOJ 机器它这个运行时间不是特别的稳定。这 QOJ 这确实稍微最近有点繁忙。
:::
AC
[https://qoj.ac/submission/2035388](https://qoj.ac/submission/2035388)
AC
[https://codeforces.com/gym/106129/submission/362933869](https://codeforces.com/gym/106129/submission/362933869)
::: 源代码
```cpp
/**
* Problem: B. Bustling Busride
* Contest: 2025
* Judge: Codeforces
* URL: https://codeforces.com/gym/106129/problem/B
* Created: 2026-02-14 18:05:23
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<>, rb_tree_tag,
tree_order_statistics_node_update>;
using ordered_pair_set = tree<pair<ll,ll>, null_type, less<>, rb_tree_tag,
tree_order_statistics_node_update>;
void Solve() {
ll N,B_stop,R_wait,W_tim;
cin >> N >> B_stop >> R_wait >> W_tim;
vector<ll> d_ls(B_stop+2);
for (ll i=1;i<=B_stop;++i) {
cin>>d_ls[i];
}
vector<ll> t_ls(N+2);
for (ll i=1;i<=N;++i) {
cin>>t_ls[i];
}
vector<ll> pre_sum(B_stop+2);
partial_sum(all(d_ls),pre_sum.begin());
auto check=[&](ll b_ans) -> bool {
ll idx=1;
// 第几班次
for (ll run=1;run<=N;++run) {
if (idx>N) {
return true;
}
ll st_run=(run-1)*R_wait;
// 该班次最大运行时间
ll mx_run=b_ans-st_run;
if (mx_run<0 && idx<=N) {
return false;
}
ll cur=0;
ordered_set pbds;
// 我们下面的注释里面详细说了为什么不需要算他的零站上去的那个情况，实际上已经被我们的二乘 pre 乘以 tim 给覆盖了。
// pbds.insert(0);
ordered_pair_set multi_pbds;
ll mx_terminal=0;
while (true) {
if (idx>N) {
return true;
}
// 我们目前是需要算，加上这个 IDX 对于我们目前运行时间的增量。
// 这个增量分为两部分，一个是我们带来的增量，就是我们给等待时间所有的带来的增量。
// 所有的站，所有在我们之前的站的等待时间（包括我们自己这一站），都需要加上我们下车的这个时间。
ll terminal=t_ls[idx];
mx_terminal=max(mx_terminal,terminal);
ll pre=pbds.order_of_key(terminal)+1;
// 你可能会说这个零站点到底是在哪里被加了呢？
// 那么其实就是在这个 add，这个2× pre 乘以 W tim 里面，就我们就加了这个零站点。
// 实际上，PRE 是包含 TERMINAL 这个站的，但是这个人在 TERMINAL 站，他下来以后就不会上去了。
// 所以二乘以 PRE，那么实际上包含他在零站上去的这个情况。他在零站上去的情况正好弥补了
// 我们多算的他在 TERMINAL 站下来的这个情况，
ll add=2*pre*W_tim;
if (pbds.find(terminal)==pbds.end()) {
// 如果这个 terminal 之前没有出现过，那么所有在其之后的也需要贡献对这个 terminal 进行贡献。
// 所以在其之后的原来就在他之后的点需要对这个 terminal 进行贡献。
// 这里我们使用一个pair 实现的 multi pbds 实现。
ll suf=SZ(multi_pbds)-multi_pbds.order_of_key({terminal,INF});
// 所有在其后面的点都需要在该站下去以后再上来，所以说是 2*suf*W_tim
add+=2*suf*W_tim;
}
if (cur+add+pre_sum[mx_terminal]>mx_run) {
break;
}
cur+=add;
pbds.insert(terminal);
multi_pbds.insert({terminal,idx});
++idx;
}
}
// 如果说大于 N 那么就说明所有的乘客都被处理完了。
return idx>N;
};
ll l=1,r=N*W_tim*(B_stop+1)+accumulate(all(d_ls),0ll);
while (l<r) {
ll mid=l+r>>1;
if (check(mid)) {
r=mid;
}else {
l=mid+1;
}
}
cout<<l<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
// cin >> lT;
// for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://qoj.ac/submission/2035388
AC
https://codeforces.com/gym/106129/submission/362933869
*/
```
:::
## 心路历程（WA，TLE，MLE……）
被 OPUS 4.6指出来的几个 bug。其实主要就是没有乘二，就是这个 pre 还有这个 suf **没有乘二**，绷不住了。忘记了，他不仅要上来，还要下去。就是他不仅要下去，还要再上来。所以相当于这个浪费还是挺多的，需要2，需要乘2。
