自动搬运

查看原文

来自洛谷，原作者为

	MaiJingYao666 格兰蚊多

搬运于2025-08-24 22:59:59，当前版本为作者最后更新于2025-05-14 14:04:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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


*/