题意

我们有一条链状的铁路系统，连接 $N$ 个城市。有 $M-1$ 天的旅行，每天从一个城市移动到相邻城市。

对于每条铁路 $i$（连接城市 $i$ 和 $i+1$），我们有三种价格：

• $A_i$：纸质票单次价格
• $B_i$：IC 卡单次价格（$B_i < A_i$）
• $C_i$：购买 IC 卡的成本

目标：选择购买哪些铁路的 IC 卡，使得总花费（购卡费 + 乘车费）最小。

关键观察

1. 决策独立性

各条铁路的 IC 卡购买决策是相互独立的，因为：

• 不同铁路的 IC 卡不能通用
• 总花费是各铁路花费的简单求和

2. 费用比较模型

对于铁路 $i$，设它被经过的次数为 $cnt_i$：

• 不买 IC 卡：总花费 = $A_i \times cnt_i$
• 买 IC 卡：总花费 = $C_i + B_i \times cnt_i$

最优决策是取两者中的较小值。

3. 核心问题转化

问题转化为：

1. 计算每条铁路被经过的次数 $cnt_i$
2. 对每条铁路独立进行费用比较

算法步骤

步骤 1：计算每条铁路的经过次数

由于铁路是链状结构，从城市 $P_j$ 到 $P_{j+1}$ 的路径是唯一的。

使用差分数组技巧：

• 初始化差分数组 diff[1..N] = 0
• 对于每个行程段 $P_j \to P_{j+1}$：
  • 设 $l = \min(P_j, P_{j+1})$, $r = \max(P_j, P_{j+1})$
  • 这表示要经过铁路 $l, l+1, \ldots, r-1$
  • 在差分数组上：diff[l] += 1, diff[r] -= 1
• 最后对差分数组求前缀和得到 $cnt_i$

步骤 2：计算最小总花费

对于 $i = 1$ 到 $N-1$：

• $cost_i = \min(A_i \times cnt_i, C_i + B_i \times cnt_i)$
• 总花费 $ans = \sum cost_i$

复杂度分析

• 步骤 1：$O(M + N)$
  • 每个行程段处理 $O(1)$
  • 前缀和计算 $O(N)$
• 步骤 2：$O(N)$
• 总复杂度：$O(N + M)$，适合 $N, M \le 10^5$

正确性证明

贪心选择的正确性

对于铁路 $i$，两种方案的费用函数：

• $f_1(cnt) = A_i \times cnt$（线性函数，斜率为 $A_i$）
• $f_2(cnt) = C_i + B_i \times cnt$（线性函数，斜率为 $B_i$）

由于 $A_i > B_i$，存在一个临界点：

• 当 $cnt$ 较小时，$f_1 < f_2$
• 当 $cnt$ 较大时，$f_2 < f_1$

临界点 $cnt_0$ 满足：

但实际上我们不需要计算临界点，直接比较两种方案的总花费即可。

总结

这道题的关键在于：

1. 识别决策独立性：各铁路独立选择是否买卡
2. 使用差分数组：高效统计经过次数
3. 简单费用比较：对每条铁路选择最优方案

算法简洁高效，时间复杂度 $O(N+M)$，能够处理大规模数据。