我将 LeetCode 1094 题（拼车）改写为了标准的 NOI/CSP 普及组/提高组风格题目。

本题是差分数组（Difference Array）在实际容量限制场景下的经典应用。

[OI 基础训练] 拼车计划 (差分数组应用)

一、 题目背景与知识点讲解

在之前的题目（如“航班预订统计”）中，我们利用差分数组解决了“多次区间修改，最后一次查询”的问题。本题在此基础上增加了一个容量限制的判断。

场景描述： 一辆车在一条路线上行驶，沿途有不同的乘客上下车。车有固定的座位数（容量）。我们需要判断在任何时刻，车上的乘客数量是否超过了容量。

1. 问题分析

• 输入：一组行程单，每个行程包含 [人数, 上车点, 下车点]，以及车的最大容量 Capacity。
• 核心逻辑：
  • 这是一个典型的区间叠加问题。
  • 对于一个行程 [num, start, end]，意味着在区间 [start, end) 内，车上的乘客数量增加了 num。
  • 注意：题目通常定义乘客在 end 点下车，这意味着在 end 这一站，这批乘客已经不在车上了。因此，占用的区间是左闭右开 [start, end)。

2. 解决方法：差分数组 由于我们需要处理大量的区间加减操作，并且只关心最终每个点的状态，差分数组是最优解。

• 定义： diff[i] 表示在地点 i，车上人数相对于地点 i-1 的变化量。

• 操作： 对于行程 (num, start, end)：

  1. 上车：在 start 站点，人数增加 num。 $\rightarrow$ diff[start] += num
  2. 下车：在 end 站点，人数减少 num（恢复原状）。 $\rightarrow$ diff[end] -= num
  • 为什么是 end 而不是 end+1？ 因为乘客在 end 点已经下车了，所以从 end 点开始，这部分人数就不占空间了。这与“闭区间更新”略有不同，需要特别注意题目对“下车点”的定义。

• 判定： 遍历差分数组，计算前缀和（即当前车上的实际人数）。如果在任何时刻，前缀和 > Capacity，则任务失败。

• 复杂度：

  • 时间复杂度：$O(N + L)$，其中 $N$ 是订单数，$L$ 是车站的最大编号。
  • 空间复杂度：$O(L)$。

二、 题目描述

ZC 城市的公交车行驶在一条笔直的公路上，公路上有一系列站点，编号从 $0$ 到 $1000$。 公交车只有 $C$ 个座位。 现在系统接到了 $N$ 个拼车订单，第 $i$ 个订单由三个整数描述：$K_i, S_i, E_i$，表示有 $K_i$ 名乘客需要在站点 $S_i$ 上车，并在站点 $E_i$ 下车。

请你判断公交车是否能够顺利完成所有订单（即在任何时刻，车上的乘客数量都不超过 $C$）。 如果可以，输出 Yes，否则输出 No。

注意： 乘客在站点 $E_i$ 下车，这意味着在站点 $E_i$ 及之后的站点，这些乘客不再占用座位。

输入格式

第一行包含两个整数 $N$ 和 $C$，分别表示订单的数量和公交车的容量。 接下来 $N$ 行，每行包含三个整数 $K_i, S_i, E_i$，表示一条订单信息。

输出格式

输出一行字符串。如果能完成所有订单输出 Yes，否则输出 No。

数据范围

• $1 \le N \le 1000$
• $1 \le C \le 10^5$
• $1 \le K_i \le 100$
• $0 \le S_i < E_i \le 1000$
• 提示：车站编号最大为 1000，不需要离散化。

样例输入 1

2 4
2 1 5
3 3 7

样例输出 1

No

样例解释 1

• 初始车上 0 人。
• 站点 1：上来 2 人（订单1），当前 2 人（$\le 4$，OK）。
• 站点 3：上来 3 人（订单2），当前 $2+3=5$ 人（$> 4$，超载！）。
• 结果：No。

样例输入 2

2 5
2 1 5
3 3 7

样例输出 2

Yes

样例解释 2

• 站点 1-2：2人。
• 站点 3-4：$2+3=5$人（$\le 5$，OK）。
• 站点 5：订单1下车，当前剩 3 人。
• 全程未超载，结果：Yes。

三、 标准代码 (C++14 OI风格)

见题解

四、 教学备课重点 (教练参考)

1. 区间定义的敏锐度：

   • 这是本题与普通区间加法（LeetCode 370）最大的区别。
   • 普通区间加法：$L$ 到 $R$ 都要加 $\rightarrow$ diff[L]+=v, diff[R+1]-=v。
   • 本题拼车：$Start$ 上车，$End$ 下车。这意味着乘客占据的是 $[Start, End-1]$ 的时间段。
   • 推导：在 $End$ 时刻，乘客消失。所以 diff[End] -= v。这一点必须向学生强调，画图演示“下车点不占座”的概念。

2. 数据范围的处理：

   • 本题车站编号较小 ($1000$)，直接开数组即可。
   • 进阶思考：如果车站编号达到 $10^9$，但订单数 $N$ 只有 $1000$，该怎么办？
     • 这涉及离散化（Discretization）或使用 std::map 来存储差分数组。这是提高组的考点，可以在学生掌握基础后顺带提一下。

3. 贪心错觉：

   • 初学者可能会尝试按开始时间排序，然后模拟。虽然可行，但写起来比差分数组麻烦（需要优先队列维护下车时间）。差分数组是此类“固定区间叠加”问题的最优雅解法。

4. 实际意义：

   • 这个模型不仅用于拼车，还广泛用于：
     • 会议室预订（判断是否冲突）。
     • 在线游戏峰值人数统计（上线时间、下线时间）。
     • 流水线任务负载分析。