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

· · 题解

题目大意

在一条单向铁路上，有 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 哦！。

代码

#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;
}