题目大意

在一条单向铁路上，有

n

个站点，有慢、快两种列车。慢车每个站点都会停，快车只会在

S_1, S_2, \dots, S_m

（其中

1 = S_1 < S_2 < \dots < S_m = n

）停靠。

现在要加入中车，快车停靠的站点它都要停，且它恰好有

k

个停靠站点。

已知快、中、慢车的速度分别为

B, C, A

（满足

B > C > A

）。

求：当合理地安排中车的停靠站点时，从 1 号站点出发，在

T

分钟内能抵达的站点（1 号站点不计）最多是多少？

分析

为了方便描述，下面把快、中车停靠站称作快车站和中车站。

因为

B > C > A

，所以先坐慢车再换乘中车或快车，肯定不如直接坐中车或快车更优。

我们先考虑两个相邻快车站之间的情况：

图中红点表示快车和中车都停靠的站点，蓝点表示仅中车停靠的站点。当我们乘坐快车或中车到达某个停靠站后，可以换乘慢车继续前进。

例如：如果在 1 号站就换乘慢车，可以走一段区间（图中橙色区间），直到时间

T

用完。假设最远到达车站

x

，那么我们可以贪心地将下一个中车停靠点设在车站

x + 1

，以避免重复计算。

这样，每次乘车都是一段区间，我们总是将停靠点设在能到达的最远站的下一站，从而保证能覆盖尽可能多的站点。

回到原题，我们暂时不考虑中车停靠站数量的限制，先像上面那样，计算出每两个快车站之间的所有区间长度，并将它们放入优先队列中。然后，我们取前

k - m

大的区间，将其长度加入答案中。当然，快车站本身对应的区间也要加入答案。

你可能会问：这样贪心是否正确？会不会出现上一个中车站的区间还没被选取，就被下一个中车站的区间"抢走"了机会？

事实上不会出现这种情况，因为上一个中车站对应的区间一定比下一个中车站的区间更长（或相等），所以优先队列会先选取更大的区间，保证贪心的正确性。

使用优先队列，时间复杂度为

O(m \log_2 m)

。

注意

题意要求不包含 1 号站，所以答案要减去 1 哦！。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+100;
ll n,m,K,A,B,C,T,ans;
ll s[N];
priority_queue<ll> q;
void init(ll l,ll r,ll t){
	if(l>r) return ;
	ll sum=0,lsum=0;
	for(int k=1;t>=0&&k<=K;k++){
		lsum=sum;
		sum+=1+t/A;
		sum=min(r-l+1,sum);
		q.push(sum-lsum);
		t+=C*lsum-C*sum;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>K;
	cin>>A>>B>>C;
	cin>>T;
	K-=m;
	for(int i=1;i<=m;i++)
		cin>>s[i];
	s[m+1]=n+1;
	ll t;
	for(int i=1;i<=m;i++){
		t=T-B*(s[i]-1);
		if(t<0) break;
		ans+=min(s[i+1]-s[i],t/A+1);
		init(s[i]+t/A+1,s[i+1]-1,t-C*(t/A+1));
	}
	for(int i=1;!q.empty()&&i<=K;i++)
		ans+=q.top(),q.pop();
	cout<<ans-1;
	return 0;
}

题解：P11791 [JOI 2017 Final] 准高速电车 / Semiexpress

文章操作

题目大意

分析

注意

代码

相关推荐

评论

题解：P11791 [JOI 2017 Final] 准高速电车 / Semiexpress