自动搬运

查看原文

来自洛谷，原作者为

	PR_CYJ 逆水行舟，不进则退

搬运于2025-08-24 21:28:01，当前版本为作者最后更新于2024-08-01 21:43:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

正着遍历一遍公路，维护 $minn$ 和 $maxx$ 两个变量，分别记录当前车流量可能的最小值和最大值。

对于每一英里的公路，总共有三种情况。

1. 当前是上匝道。此时就将 $minn$ 加上当前路段车流量的下限 $dw_i$，将 $maxx$ 加上当前路段车流量的上限 $uw_i$。
2. 当前是主路。此时车流量的下限就是 $\max(minn,dw_i)$，上限则是 $\min(maxx,uw_i)$。
3. 当前是下匝道。此时就将 $minn$ 减去当前路段车流量的上限，将 $maxx$ 减去当前路段车流量的下限 $dw_i$。

这样正着遍历一遍公路，就得出了第 $n$ 公里后车流量的上限和下限。

对于第 $1$ 公里前的车流量的上限和下限，我们在反着跑一遍，就可以得到答案了。但是此时三种情况的处理方式有所变化。

1. 当前是上匝道。因为我们是反着遍历的，所以可以将其看作车辆下高速。因此就将 $minn$ 更新为 $minn-uw_i$，将 $maxx$ 更新为 $maxx-dw_i$。
2. 当前是主路。此时的更新方式和正着遍历是一样，将 $minn$ 更新为 $\max(minn,dw_i)$，将 $maxx$ 更新为 $\min(maxx,uw_i)$。
3. 当前是下匝道。因为是反着遍历，所以可以将其看作车辆上高速。因此就将 $minn$ 更新为 $minn+dw_i$，将 $maxx$ 更新为 $maxx+uw_i$。

注意 $minn$ 和 $maxx$ 在遍历过程中可能会小于 $0$，因此要取 $\max(minn,0)$ 和 $\max(maxx,0)$。

代码

切勿抄袭！！！

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,minn,maxx=100000,op[N],dw[N],uw[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string t;
		cin>>t>>dw[i]>>uw[i];
		if (t=="on")
			op[i]=1;
		else if (t=="none")
			op[i]=2;
		else
			op[i]=3;
	}
	for(int i=n;i>=1;i--)//反着遍历高速公路，得出第一公里前车流量的上限和下限
	{
		if (op[i]==1)
		{
			minn-=uw[i];
			maxx-=dw[i];
			minn=max(minn,0);
			maxx=max(maxx,0);//注意 minn 和 maxx 可能会小于0
		}
		else if (op[i]==2)
		{
			minn=max(minn,dw[i]);
			maxx=min(maxx,uw[i]);
		}
		else
		{
			minn+=dw[i];
			maxx+=uw[i];
		}
	}
	cout<<minn<<" "<<maxx<<"\n";
	minn=0;
	maxx=100000;//注意要将变量重新设为初始值
	for(int i=1;i<=n;i++)//正着遍历高速公路，得出第 n 公里后车流量的上限和下限
	{
		if (op[i]==1)
		{
			minn+=dw[i];
			maxx+=uw[i];
		}
		else if (op[i]==2)
		{
			minn=max(minn,dw[i]);
			maxx=min(maxx,uw[i]);
		}
		else
		{
			minn-=uw[i];
			maxx-=dw[i];
			minn=max(minn,0);
			maxx=max(maxx,0);//注意 minn 和 maxx 可能会小于0
		}
	}
	cout<<minn<<" "<<maxx<<"\n";
}