题解：P10654 [ROI 2017] 水星上的服务器 (Day 2)

· · 题解

P10654 [ROI 2017] 水星上的服务器 (Day 2) 题解

不难想的一道思维题。

解题思路

刚开始看有点复杂，但发现显然这是一条链，所以要考虑的就是信息往左传递的时间和往右传递的时间。我们设 [ll_i,lr_i],[rl_i,rr_i] 分别表示第 i 号节点向左传递和向右传递的时间阀。显然 ll_1=0,lr_1=+\infin，同时 rl_n=0,rr_n=+\infin。+\infin 取 10^9 就行了。
考虑转移，首先先看一下无解的情况。向左传递时如果节点 i 和节点 i-1 之间的边最久时间比 ll_{i-1} 小，或者最近时间比 lr_{i-1} 小，显然就无法传递，同时，第 i 号节点到第 n 号节点也无法传递。向右传递同理。
那么怎么正常转移呢？还是以向左转移为例，首先，lr_i=\max(lr_{i-1},r_i)。不难理解，因为第一时间的性质，所以我们发送的时间就是两者之中的最小值。ll_i 的转移就需要点思考，如果 ll_{i-1}>l_i，因为如果这时候提前发送，那么因为第一时间的性质，就会导致不在下一个节点的正确时间内传递，所以这时候 ll_i=ll_{i-1}。但如果 ll_{i-1}\le l_i，那么就可以利用缓冲区 t_i，ll_i=\max(l_i-t_i,0)。
最后就是我们把向左向右的推出来了，怎么确定呢？显然当两个区间没有交集时，没办法周全，那就是 -1。否则，取交集的左端点，推一下就知道是 \max(ll_i,rl_i)。就做出来了。

AC 代码

#include<iostream>
using namespace std;
const int N=2e5+5;
const int Maxn=1e9;
int n;
int t[N];
int l[N],r[N];
int ll[N],lr[N],rl[N],rr[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
    }
    for(int i=1;i<n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    ll[1]=0,lr[1]=Maxn;
    for(int i=2;i<=n;i++){
        if(l[i-1]>lr[i-1] || r[i-1]<ll[i-1]){
            for(int j=i;j<=n;j++){
                ll[j]=-1;
                lr[j]=-1;
            }
            break;
        }
        lr[i]=min(lr[i-1],r[i-1]);
        if(ll[i-1]<=l[i-1]) ll[i]=max(0,l[i-1]-t[i]);
        else ll[i]=ll[i-1];
    }
    rl[n]=0,rr[n]=Maxn;
    for(int i=n-1;i>=1;i--){
        if(l[i]>rr[i+1] || r[i]<rl[i+1]){
            for(int j=i;j>=1;j--){
                rl[j]=-1;
                rr[j]=-1;
            }
            break;
        }
        rr[i]=min(rr[i+1],r[i]);
        if(rl[i+1]<=l[i]) rl[i]=max(0,l[i]-t[i]);
        else rl[i]=rl[i+1];
    }
    for(int i=1;i<=n;i++){
//      cout<<ll[i]<<" "<<lr[i]<<" "<<rl[i]<<" "<<rr[i]<<" ";
        if(ll[i]==-1 || rl[i]==-1 || ll[i]>rr[i] || rl[i]>lr[i]){
            printf("-1\n");
        }
        else  printf("%d\n",max(ll[i],rl[i]));
    }
}
/*
a~b
c~d

*/