专栏文章

题解：P1695 [USACO19FEB] Measuring Traffic B

NNKOJ_AKer
P1695题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq7te32
此快照首次捕获于
2025/12/04 00:22
3 个月前
此快照最后确认于
2025/12/04 00:22
3 个月前
查看原文

题目传送门

题意

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

思路

我们先考虑一英里前的车辆范围。为了保证范围一定可靠，所以我们要尽量保证下限更小，上限更大。接下来我们分情况讨论
令下限为 minnminn ,上限为 maxnmaxn ， ai.xa_i.x为 ii 英里时下限， ai.ya_i.y 为 ii 英里时的上限 。
从后往前遍历一遍
  • 当现在处于上匝道时， minn−ai.y,maxn−ai.xminn-a_i.y,maxn-a_i.x；
  • 当现在处于下匝道时，minn+ai.x,maxn+ai.yminn+a_i.x,maxn+a_i.y；
  • 当现在处于主干道时，minn=max(ai.x,minn),maxn=min(ai.y,maxn)minn=max(a_i.x,minn),maxn=min(a_i.y,maxn) 。
这样我们就得到了一英里前的车辆范围。同理，我们只需要将循环顺序倒转一遍就可得n英里后的车辆范围。
令下限为 minnminn ,上限为 maxnmaxn ， ai.xa_i.x为 ii 英里时下限， ai.ya_i.y 为 ii 英里时的上限 。
从前往后遍历一遍
  • 当现在处于上匝道时，minn+a[i].x,maxn+=a[i].yminn+a[i].x,maxn+=a[i].y ；
  • 当现在处于下匝道时，minn−a[i].y,maxn−=a[i].xminn-a[i].y,maxn-=a[i].x ；
  • 当现在处于主干道时minn=max(a[i].x,minn),maxn=min(a[i].y,maxn)minn=max(a[i].x,minn),maxn=min(a[i].y,maxn) 。

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

代码展板

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...