2020牛客NOIP赛前集训营-提高组（第二场）D 移动

文章目录

$Result$$Hyperlink$$Description$$Solution$$Code$

$Result$

---

$Hyperlink$

https://ac.nowcoder.com/acm/contest/7607/D

---

$Description$

有$n$扇门，你要从第0扇门出发，到达第$n+1$个位置，位移出一个位置需要1s 有$m$个限制，每个限制$(a,b,c)$告诉你，第$a$扇门将在$[b,c]$时段中关闭 问到达$n+1$的最小时间

数据范围：$n,m\le 10^5,b\le c\le 10^9$

---

$Solution$

$85pts$ 记录每个位置的限制条件，设$t$表示运动到$i+1$扇门的最短时间 考虑到每个限制条件，如果$t$恰好位于关闭期间，则它必须在$R+1$时刻

如果$t$没有受到限制，则$t=t+1$

时间复杂度：$O(n+m)$

$100pts$ $dp$做法，设$f_{i,j}$表示运动到离散化后的第$i$个时刻，能否到达$j$位置，用堆维护转移即可

---

$Code$

$85pts$

#include<cctype> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #define LL long long using namespace std;int n,m,a,b,c,ti,t; vector<int>L[200010],R[200010]; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } signed main() { n=read();m=read(); for(register int i=1;i<=m;i++) a=read(),b=read(),c=read(),L[a].push_back(b),R[a].push_back(c); t=1; for(register int i=1;i<=n;i++) { ti=t; for(register int j=0;j<L[i].size();j++) if(t>=L[i][j]&&t<=R[i][j]) t=R[i][j]+1; if(t==ti) t++; } printf("%d",t+1); }