洛谷P3046 海底高铁 -差分统计经过区间次数
题目贴在这里P3406 海底高铁 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析
本题题干很长，但是题意理解很简单。就是给定n个节点，每次仅能在相邻的两个节点之间移动，且任意两个节点之间的高铁费用也不一样。
依据题意，假设从3节点到1节点，我们要走两段路，即从3->2 , 2->1。
对于每段路，有两种收费模式，一个是直接买票，另一个是办卡。
最后要求我们给出最少的花费
显然我们可以先根据路线统计出通过各个路段的次数。
如从3->1，经过1-2路段次数加1，经过2-3的次数加1。
最后用各个路段经过次数乘以花费，即sum = max(cnt * 买票 ，cnt * 办卡花费 + 工本费)
但是如果我们遍历区间来进行一段一段的计数的话，时间复杂度有点高，大概是O(N2)
仔细观察，统计3->1经过的路段的次数，无非是将区间1-3或者说第一段路到第二短路所有元素加1（此时编号1-2）。要简化这种操作，只需要求出原路段数组的差分数组，对其差分数组进行操作即可，最后再求一遍前缀和，即可得出加1后的路段次数数组。
而且更加方便的是，初始时所有路段经过次数都为0，故其差分数组就是一个元素都为0 的数组。所以我们只需要读入每次经过的区间，对差分数组进行插入操作即可。读入所有区间之后在进行求前缀和，这样就得到每段路所经过的次数了。
AC代码如下
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int F = 1e5 + 10;
ll N, M;
ll P[F];
ll All[F];
ll D[F];
ll A[F];
ll B[F];
ll C[F];
//差分
void Insert(int l ,int r)
{
D[l] += 1;
D[r + 1] -= 1;
}
int main()
{
cin >> N >> M;
for (int i = 1; i <= M; i++)
{
cin >> P[i];
}
for (int i = 1; i <= N - 1; i++)
{
cin >>A[i]>>B[i]>>C[i];
}
for (int i = 1; i <= M-1; i++)
{
int x = P[i];
int y = P[i + 1];
if (x > y)swap(x, y);
y -= 1;
Insert(x, y);
}
for (int i = 1; i <= N-1; i++)
{
All[i] = All[i-1]+D[i];
}
ll Sum = 0;
for (int i = 1; i <= N-1; i++)
{
Sum += min(All[i] * A[i],All[i]*B[i]+C[i]);
}
cout << Sum;
return 0;
}