鉄道旅行 (Railroad Trip)

题意

有 $n$ 个城市， $n-1$ 条道路。其中第 $i$ 个城市和第 $i+1$ 个城市由第 $i$ 条道路连接。通过一条道路有两种付费方式：每次支付费用 $a_i$ ，或者支付一次费用 $c_i$ ，然后每次支付费用 $b_i$ 。

$m-1$ 次旅行，第 $j$ 次旅行从城市 $p_{j}$ 到城市 $p_{j+1}$ 。

求完成旅行所需的最小费用。

分析与解答

发现每条道路对答案的影响是独立的。

考虑统计一段道路被经过的次数，然后对于每段道路在两种方案中取最小即可。

对于每次旅行都把所有经过道路的经过次数 $+1$ ，最后统计即可。

那么这就是一个区间修改，单点查询的问题。

所以差分一下就好了。

注意这里统计的是起点和终点间的边经过的数量，所以每次把一段旅行的起止点中标号较小的城市在差分数组中 $+1$，标号较大的城市在差分数组中 $-1$ 即可。

时间复杂度 $ \Theta(n)$

就做完了，就这么简单

代码中无意间卡空间，请见谅。

Code

#include <cstdio>

#include <iostream>

#define RE register

using namespace std;

inline int read()

{

	int x = 0; char c = getchar();

	while(c<'0'||c>'9') c = getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x;

}

inline int min(int a, int b){return a<b?a:b;}

inline int max(int a, int b){return a>b?a:b;}

const int MAXN = 100010;

int n, m;

int d[MAXN];

int main()

{

	n = read(); m = read();

	RE int now, last = 0;

	for(RE int i=1;i<=m;i++)

	{

		now = read();

		if(last) ++d[min(last, now)], --d[max(last, now)];

		// 差分，标号较小的 +1 ，标号较大的 -1

		last = now;

	}

	for(RE int i=1;i<n;i++)

		d[i] += d[i-1]; // 还原成真正的经过次数

	long long ans = 0;

	for(RE int i=1;i<n;i++)

	{

		RE int a = read(), b = read(), c = read();

		ans += min(1ll*a*d[i], 1ll*d[i]*b+c);

		// 直接计算费用，每条道路取最小。

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

鉄道旅行 (Railroad Trip)

题意

分析与解答

Code

最新文章

热门文章