题解：P1695 [USACO19FEB] Measuring Traffic B

Noheaven · 2025-02-19 21:45:51 · 题解

题目传送门

题意

给定一条高速公路，描述每一英里的情况。如果这一英里内有一条上匝道，则返回经过上匝道的车数范围，如果有下匝道，则返回经过下匝道的车数范围，如果两者都没有，则返回经过主干道的车数范围。题目要求你输出1英里以前的车辆范围以及n英里以后的车辆范围。

思路

我们先考虑一英里前的车辆范围。为了保证范围一定可靠，所以我们要尽量保证下限更小，上限更大。接下来我们分情况讨论

令下限为 minn ,上限为 maxn ， a_i.x为 i 英里时下限， a_i.y 为 i 英里时的上限 。

从后往前遍历一遍

• 当现在处于上匝道时， minn-a_i.y,maxn-a_i.x；
• 当现在处于下匝道时，minn+a_i.x,maxn+a_i.y；
• 当现在处于主干道时，minn=max(a_i.x,minn),maxn=min(a_i.y,maxn) 。

这样我们就得到了一英里前的车辆范围。同理，我们只需要将循环顺序倒转一遍就可得n英里后的车辆范围。

令下限为 minn ,上限为 maxn ， a_i.x为 i 英里时下限， a_i.y 为 i 英里时的上限 。

从前往后遍历一遍

• 当现在处于上匝道时，minn+a[i].x,maxn+=a[i].y ；
• 当现在处于下匝道时，minn-a[i].y,maxn-=a[i].x ；
• 当现在处于主干道时minn=max(a[i].x,minn),maxn=min(a[i].y,maxn) 。

注：计算过程中可能出现负数记得和 0 取最大值！！

代码展板

#include<bits/stdc++.h>
using namespace std;
typedef int intt;
#define int long long
int n,minn,maxn=0x3f3f3f3f3
struct node{
    int x,y;
    string s;
}a[105]
signed main(){
    ios::sync_with_stdio(false)
    cin.tie(0)cout.tie(0)
    cin>>n
    for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].x>>a[i].y
    for(int i=n;i>=1;i--){//求一英里前的车辆范围 
        if(a[i].s=="on")minn-=a[i].y,maxn-=a[i].x,minn=max(minn,0ll),maxn=max(maxn,0ll)
        if(a[i].s=="off")minn+=a[i].x,maxn+=a[i].y
        if(a[i].s=="none")minn=max(a[i].x,minn),maxn=min(a[i].y,maxn)
    }
    cout<<minn<<" "<<maxn<<"\n"
    minn=0,maxn=0x3f3f3f3f3
    for(int i=1;i<=n;i++){//n英里后的车辆范围
        if(a[i].s=="on")minn+=a[i].x,maxn+=a[i].y
        if(a[i].s=="off")minn-=a[i].y,maxn-=a[i].x,minn=max(minn,0ll),maxn=max(maxn,0ll)
        if(a[i].s=="none")minn=max(a[i].x,minn),maxn=min(a[i].y,maxn)
    }
    cout<<minn<<" "<<maxn<<"\n"
    return 0;
}