洛谷 P3406 海底高铁（差分，前缀和）()

题目分析

这题一看就知道是要用到前缀和，但我傻傻的以为前缀和应该求的是i到n-1段铁路车票钱，于是在每一段铁路应该选择纸质车票还是IC卡犯了难……

其实可以换一个思路，我们去考虑经过每一段铁路的次数，每经过一次铁路就将当前铁路经过的次数加一，再最后再考虑到底是选纸质车票还是IC卡更好

由于对一段路程内经过的每个铁路的次数加一的操作太耗时，我们可以利用差分的思想对铁路的次数进行修改，最后求一遍前缀和就得到了每段铁路经过的次数

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
long long d[N];	// 记得开long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	int now, prev;	// now为当前城市，prev为前一个城市
	cin >> prev;	// 预先将第一个城市存到prev中
	for (int i = 1; i <= m - 1; i ++ )	// 注意我们之前已经读入了第一个城市，还剩下m - 1个城市未读入
	{
		// 需注意now和prev是城市的编号，l和r是铁路的编号，需要将城市编号换算为铁路编号
		// 画图可以发现，l在靠左的城市右边，r在靠右城市的左边
		// l与靠左城市的编号相同，r比靠右城市的编号少1
		cin >> now;
		int l = min(now, prev), r = max(now, prev) - 1;	// 确保l在r的左边，方便差分
		d[l] ++, d[r + 1] --;
		prev = now;	// 更新prev
	}
	
	long long sum = 0;
	for (int i = 1; i <= n - 1; i ++ )
	{
		d[i] += d[i - 1];	// 由差分得到铁路经过次数
		int a, b, c;
		cin >> a >> b >> c;
		sum += min(a * d[i], b * d[i] + c);	// 比较纸质车票与IC卡，选择两者中更划算的
	}
	
	cout << sum << '\n';
	
	return 0;
}
————————

题目分析

这题一看就知道是要用到前缀和，但我傻傻的以为前缀和应该求的是i到n-1段铁路车票钱，于是在每一段铁路应该选择纸质车票还是IC卡犯了难……

其实可以换一个思路，我们去考虑经过每一段铁路的次数，每经过一次铁路就将当前铁路经过的次数加一，再最后再考虑到底是选纸质车票还是IC卡更好

由于对一段路程内经过的每个铁路的次数加一的操作太耗时，我们可以利用差分的思想对铁路的次数进行修改，最后求一遍前缀和就得到了每段铁路经过的次数

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
long long d[N];	// 记得开long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	
	int now, prev;	// now为当前城市，prev为前一个城市
	cin >> prev;	// 预先将第一个城市存到prev中
	for (int i = 1; i <= m - 1; i ++ )	// 注意我们之前已经读入了第一个城市，还剩下m - 1个城市未读入
	{
		// 需注意now和prev是城市的编号，l和r是铁路的编号，需要将城市编号换算为铁路编号
		// 画图可以发现，l在靠左的城市右边，r在靠右城市的左边
		// l与靠左城市的编号相同，r比靠右城市的编号少1
		cin >> now;
		int l = min(now, prev), r = max(now, prev) - 1;	// 确保l在r的左边，方便差分
		d[l] ++, d[r + 1] --;
		prev = now;	// 更新prev
	}
	
	long long sum = 0;
	for (int i = 1; i <= n - 1; i ++ )
	{
		d[i] += d[i - 1];	// 由差分得到铁路经过次数
		int a, b, c;
		cin >> a >> b >> c;
		sum += min(a * d[i], b * d[i] + c);	// 比较纸质车票与IC卡，选择两者中更划算的
	}
	
	cout << sum << '\n';
	
	return 0;
}