【USACO19FEB Bronze】Measuring Traffic

USACOの模拟小题。

题目详情

原题链接（英文题面）：http://www.usaco.org/index.php?page=viewproblem2&cpid=917

中文翻译：
Farmer John的农场边上的高速公路最近出现了引人注目的流量上升，或者至少Farmer John看起来是这样的。为了证实这件事，他打算用一组传感器测量公路上的车流量，每个传感器被用来测量一小段路面上的车流量的数值。

不幸的是，某一天经过牛棚的时候，Farmer John被绊倒了，装有传感器的盒子掉进了一个巨大的奶缸，之后它们就不能正常工作了。比起之前可以产生一个精确的车流量读数，现在每个传感器只能输出一个可能结果的范围。例如，一个传感器可能会给出范围 $[7,13]$ ，表示在这段路面上的车流量不小于 $7$ ，并且不大于 $13$ 。

高速公路经过农场的这一段长 $N$ 英里，车辆仅从一个方向通过公路，从第1英里驶向第 $N$ 英里。Farmer John想要安装N个传感器——每一个监测高速公路上1英里长的路段。在其中某些路段上，有能够使得车辆进入高速公路的上匝道；在所有这样的路段上，Farmer John会将传感器装在上匝道上，测量流入的（近似）车流量。在某些路段上有能够使得车辆离开高速公路的下匝道；在所有这样的路段上，Farmer John会将传感器装在下匝道上。每一个路段包含至多一个匝道。如果在公路的一个路段上没有上匝道或下匝道，Farmer John就将传感器装在高速公路的主路上。

给定Farmer John的 $N$ 个传感器的读数，请求出在高速公路第1英里之前和第 $N$ 英里之后车流量的最为准确的可能范围。这些范围应当与所有 $N$ 个传感器的读数相一致。

做法

处理两次，第一次从后往前确定一个范围（即1公里时的车流量），而第二次反过来，从前往后确定范围（得出 $N$ 公里时的车流量）即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[105],b[105];
string status[105]; 
int main(){
	// freopen("traffic.in","r",stdin);
	// freopen("traffic.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>status[i]>>a[i]>>b[i];	 
	int left=INT_MIN,right=INT_MAX;
	for(int i=n;i>=1;i--) {//从后往前
		if(status[i]=="none"){
			left=max(left,a[i]);
			right=min(right,b[i]);
		}
		if(status[i]=="off"){
			left+=a[i];
			right+=b[i];
		}
		if(status[i]=="on"){
			left-=b[i];
			right-=a[i];
			left=max(0,left);
		}
	}
	cout<<left<<' '<<right<<endl;
	left=INT_MIN,right=INT_MAX;
	for(int i=1;i<=n;i++){//从前往后
		if(status[i]=="none"){
			left=max(left,a[i]);
			right=min(right,b[i]);
		}
		if(status[i]=="on"){
			left+=a[i];
			right+=b[i];
		}
		if(status[i]=="off"){
			left-=b[i];
			right-=a[i];
			left=max(0,left);
		}
	}
	cout<<left<<' '<<right<<endl;
	return 0;
}