洛谷P3406题：贪心算法与差分数组解决海底高铁问题

一、问题分析

Uim需要在多个城市间出差，每段铁路可以选择购买纸质票或IC卡。我们需要计算在访问所有指定城市后，包括购票、买卡和充值在内的最小总花费。

二、算法思路

1. ‌统计每段铁路的使用次数‌：使用差分数组高效计算

2. ‌最优决策‌：对每段铁路，比较IC卡和纸质票的总花费

3. ‌计算最小总花费‌：根据使用次数选择更经济的方案

三、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    vector<int> P(M);
    for(int i = 0; i < M; ++i) {
        cin >> P[i];
    }
    
    vector<int> diff(N + 2, 0); // 差分数组
    
    // 计算每段铁路的使用次数
    for(int i = 1; i < M; ++i) {
        int start = min(P[i-1], P[i]);
        int end = max(P[i-1], P[i]);
        diff[start]++;
        diff[end]--;
    }
    
    // 计算前缀和得到每段铁路的实际使用次数
    vector<int> count(N, 0);
    int current = 0;
    for(int i = 1; i < N; ++i) {
        current += diff[i];
        count[i] = current;
    }
    
    long long total = 0;
    for(int i = 1; i < N; ++i) {
        int A, B, C;
        cin >> A >> B >> C;
        // 比较两种方案的花费
        long long paper_cost = (long long)count[i] * A;
        long long ic_cost = (long long)count[i] * B + C;
        total += min(paper_cost, ic_cost);
    }
    
    cout << total << endl;
    return 0;
}

四、算法详解

1. 输入处理

读取城市数量N和访问城市数量M，以及访问顺序P数组。

2. 差分数组计算

• 初始化差分数组diff

• 对于每段行程，标记起点和终点

• 计算前缀和得到每段铁路的实际使用次数count

3. 最优决策

对于每段铁路：

• 计算全部使用纸质票的总花费

• 计算使用IC卡的总花费（包括工本费）

• 选择两者中较小的值累加到总花费

4. 输出结果

输出计算得到的最小总花费。

五、总结

通过这个问题，我们学习了如何用差分数组高效统计区间使用次数，以及如何用贪心算法做出局部最优决策。这种技术可以广泛应用于需要统计区间信息和做最优决策的问题中。掌握这种算法思想对解决实际生活中的优化问题有很大帮助。