算法基础篇：一维差分专题与实战应用

方法二：严格根据定义构建

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int f[N];
int a[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) f[i] = a[i] - a[i - 1];
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        f[l] += k;
        f[r + 1] -= k;
    }
    for (int i = 1; i <= n; i++) {
        f[i] += f[i - 1];
        cout << f[i] << " ";
    }
    return 0;
}

3.2 海底高铁

题目描述

有 n 个城市，m 次访问记录。每次访问从城市 p_i 到 p_{i+1}。每条路段有三种收费方式：按次买票、办卡（含工本费）、其他。求最小总花费。

算法原理

1. 计算最小花费：每段路被乘坐的次数记作 f[i]。最小花费为 min(按次花费，办卡花费)。
   • 按次花费：a[i] * f[i]
   • 办卡花费：b[i] * f[i] + c[i]
2. 统计乘坐次数：利用差分数组统计每段路的使用频率。
   • 创建全 0 差分数组。
   • 遍历访问序列，对于每次访问 p_i -> p_{i+1}，区间 [min(p_i, p_{i+1}), max(p_i, p_{i+1}) - 1] 加 1。
   • 注意：如果 p_i > p_{i+1}，需交换顺序。
   • 最后对差分数组做前缀和得到实际次数。

代码实现

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL f[N];

int main() {
    LL n, m;
    cin >> n >> m;
    LL x;
    cin >> x;
    for (int i = 2; i <= m; i++) {
        LL y;
        cin >> y;
        // x -> y
        if (y > x) {
            f[x]++;
            f[y]--;
        } else {
            f[x]--;
            f[y]++;
        }
        x = y;
    }
    for (int i = 1; i < n; i++) f[i] += f[i - 1];
    
    LL ret = 0;
    for (int i = 1; i < n; i++) {
        LL a, b, c;
        cin >> a >> b >> c;
        ret += min(a * f[i], c + b * f[i]);
    }
    cout << ret << endl;
    return 0;
}

提示：在实际开发中，处理大规模数据区间更新时，务必优先考虑差分或线段树等数据结构，避免 O(n*m) 的暴力解法导致超时。