本文共 1621 字，大约阅读时间需要 5 分钟。
大意: 给定$n$张卡$(a_i,b_i,c_i,d_i)$, 初始坐标$(0,0)$.
假设当前在$(x,y)$, 若$x\ge a_i,y\ge b_i$, 则可以使用第$i$张卡, 使用后达到坐标$c_i,d_i$.
求最少使用多少张卡后才能使用最后一张卡.
直接$BFS$的话是$O(n^2)$的, 用数据结构优化即可.
#include #include #include #include #include #define REP(i,a,n) for(int i=a;i<=n;++i)#define PER(i,a,n) for(int i=n;i>=a;--i)#define hr putchar(10)#define lc (o<<1)#define rc (lc|1)#define mid ((l+r)>>1)#define ls lc,l,mid#define rs rc,mid+1,r#define x first#define y secondusing namespace std;typedef pair pii;typedef tuple t3;const int N = 1e6+10;const int INF = 0x3f3f3f3f;int n, cnt, b[N], pre[N];struct {int a,b,c,d,id;} a[N];queue q;priority_queue ,greater > s[N];pii tr[N<<2];int ID(int x) { return lower_bound(b+1,b+1+*b,x)-b;}void dfs(int x) { ++cnt; if (pre[x]!=-1) dfs(pre[x]); else printf("%d\n",cnt); printf("%d ",x);}void build(int o, int l, int r) { if (l==r) { tr[o].x = s[l].empty()?INF:s[l].top().x; tr[o].y = l; return; } build(ls),build(rs); tr[o]=min(tr[lc],tr[rc]);}void update(int o, int l, int r, int x) { if (l==r) { tr[o].x = s[l].empty()?INF:s[l].top().x; return; } mid>=x?update(ls,x):update(rs,x); tr[o]=min(tr[lc], tr[rc]);}pii find(int o, int l, int r, int ql, int qr) { if (ql<=l&&r<=qr) return tr[o]; if (mid>=qr) return find(ls,ql,qr); if (mid x) break; while (s[ret.y].size()&&s[ret.y].top().x<=x) { int id2 = s[ret.y].top().y; s[ret.y].pop(); pre[id2] = id; q.push(t3(a[id2].c,a[id2].d,id2)); } update(1,1,*b,ret.y); } } if (!pre[n]) return puts("-1"),0; dfs(n),hr;}
转载于:https://www.cnblogs.com/uid001/p/11196998.html