USACOの模拟小题。

题目详情

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

中文翻译:

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

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

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

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

做法

处理两次,第一次从后往前确定一个范围(即1公里时的车流量),而第二次反过来,从前往后确定范围(得出 NN 公里时的车流量)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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;
}