「NOI2018模拟6」红绿灯 - 线段树+动态规划 | Bill Yang's Blog

「NOI2018模拟6」红绿灯 - 线段树+动态规划

题目大意


题目分析

考虑,我们只需要计算出每个人出发后什么时候会遇到红灯,剩下的都是规律性的移动了。
不妨计算出$f(i)$表示从第$i$个红绿灯到达学校所需时间。
计算$f(i)$的方法与处理询问类似,从后往前递推,找到后面第一个遇到红灯的地方计算。

那么现在的问题变为了如何寻找第一个遇到红灯的位置。
对于一个从$t_i$时间从家出发的人,满足:

即:

这是一段区间,用线段树维护一下即可。
转移时的区间与此类似,不再赘述。


代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=50005;
struct Segment_Tree {
struct Tree {
int ls,rs,min;
Tree() {ls=rs=0;min=INT_MAX/2;}
} tree[maxn*50];
int size;
#define mid ((left+right)>>1)
void insert(int &index,int left,int right,int tar,int val) {
if(right<tar||left>tar)return;
if(!index)index=++size;
tree[index].min=min(tree[index].min,val);
if(left==right)return;
insert(tree[index].ls,left,mid,tar,val);
insert(tree[index].rs,mid+1,right,tar,val);
}
int query(int index,int left,int right,int Left,int Right) {
if(!index||Right<left||Left>right)return INT_MAX/2;
if(Left<=left&&Right>=right)return tree[index].min;
return min(query(tree[index].ls,left,mid,Left,Right),query(tree[index].rs,mid+1,right,Left,Right));
}
} st;
int n,q,root;
LL g,r,d[maxn],f[maxn];
int main() {
n=Get_Int();
g=Get_Int();
r=Get_Int();
for(int i=1; i<=n+1; i++)d[i]=d[i-1]+Get_Int();
for(int i=n; i>0; i--) {
int next=min(st.query(root,0,g+r,g+d[i]%(g+r),g+r-1+d[i]%(g+r)),st.query(root,0,g+r,d[i]%(g+r)-r,-1+d[i]%(g+r)));
if(next==INT_MAX/2)f[i]=d[n+1]-d[i];
else f[i]=f[next]+((d[next]-d[i]-1)/(g+r)+1)*(g+r);
st.insert(root,0,g+r,d[i]%(g+r),i);
}
q=Get_Int();
while(q--) {
int t=Get_Int();
int next=min(st.query(root,0,g+r,g-t%(g+r),g+r-1-t%(g+r)),st.query(root,0,g+r,g-t%(g+r)+(g+r),g+r-1-t%(g+r)+(g+r)));
if(next==INT_MAX/2)printf("%lld\n",d[n+1]+t);
else printf("%lld\n",f[next]+((d[next]+t-1)/(g+r)+1)*(g+r));
}
return 0;
}
0%