Luogu P3406 海底高铁 解题报告

题目链接:P3406 海底高铁

题目分析:

(第一眼以为是最短路) 这道题作为前缀和的练习挺不错的,因为它几乎不涉及其他算法

​ 首先根据题目中的信息进行数据读入:不开long long见祖宗(这题貌似不会)

1
2
3
4
5
6
7
8
9
ll n,m,ans=0;//共N个城市,途经M个城市
scanf("%lld%lld",&n,&m);
ll p[m+1];//访问顺序
ll t[n+1]={};//经过次数,一定要初始化!
ll a[n+1],b[n+1],c[n+1],x,y;//a[i]纸质单程票,b[i]办卡后的优惠价,c[i]办卡工本费
for(ll i=1;i<=m;i++)
scanf("%lld",&p[i]);
for(ll i=1;i<=n-1;i++)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);

​ 由于第i段铁路连接了城市i和城市i+1,所以任意两个相邻的站点购买同种车票有且仅有一种费用,也就是说,价格仅与在某相邻两站之间的通过次数有关。此时,我们就将问题转化为求在给定路线下,每相邻两个站点路段的经过次数.

​ 那么,在出发之前,我们可以将每两站之间路段的经过次数全部初始化为0,然后,对每次给定的始发站和终到站,将其视作给定区间的两个端点,对此区间进行区间增操作。

如何进行区间增呢???

首先这是给定的四个站点

​ 如果我们按照1-3,3-2,2-4,4-3的顺序访问,可以发现四个站点间的路径经过次数是这样的:

路径 1-2 2-3 3-4
次数 1 3 2

​ 一般的思路是,对于每个区间,用一个for对其所经次数++,然而我们发现,太慢了

​ 于是我们想到了前缀和

对于每一个区间,我们可以在其左端点加上区间增的权值,再在右端点+1的位置减去区间增的权值,最后对该区间进行求前缀和操作。这样,我们可以得到一样的结果。

回到题目中

​ 恍然大悟,对于每组给定的区间端点,也可以使用同样的方法。更方便地,我们可以在对所有区间端点处理完毕后,在进行求前缀和操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
	//由于给定的信息是端点(城市),但是要求的是区间(路段),所以循环次数应为城市数-1
for(ll i=1;i<=m-1;i++){
//对于端点的处理,要严格满足数学上的定义,小的在左端点,大的在右端点
//否则对于逆序信息,就相当于进行了区间减操作
if(p[i]>p[i+1]){
x=p[i+1];
y=p[i];
}
else{
x=p[i];
y=p[i+1];
}
//上面的代码可以简写为:
//x=min(p[i],p[i+1]);
//y=max(p[i],p[i+1]);
t[x]++;//左端点增
t[y]--;//右端点减
}
//求前缀和
for(ll i=1;i<=n;i++){
t[i]+=t[i-1];
}

​ 最后,对于每一段路径,总价值加上该段路径费用的较小值。

1
2
for(ll i=1;i<=n-1;i++)
ans+=min(a[i]*t[i],(b[i]*t[i]+c[i]));

​ 本题就解决啦!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<algorithm>
#include<iostream>
#define ll long long
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;
int main(){
ll n,m,ans=0;
scanf("%lld%lld",&n,&m);
ll p[m+1];
ll t[n+1]={};
ll a[n+1],b[n+1],c[n+1],x,y;
for(ll i=1;i<=m;i++)
scanf("%lld",&p[i]);
for(ll i=1;i<=n-1;i++)
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
for(ll i=1;i<=m-1;i++){
if(p[i]>p[i+1]){
x=p[i+1];
y=p[i];
}
else{
x=p[i];
y=p[i+1];
}
t[x]++;
t[y]--;
}
for(ll i=1;i<=n;i++){
t[i]+=t[i-1];
}
for(ll i=1;i<=n-1;i++)
ans+=min(a[i]*t[i],(b[i]*t[i]+c[i]));
printf("%lld",ans);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×