P1695题解

· · 题解

题目传送门

思路

正着遍历一遍公路，维护 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";
}