- 5194: [Usaco2018 Feb]Snow Boots
- Time Limit: 10 Sec Memory Limit: 128 MB
- Submit: 102 Solved: 79
- [Submit][Status][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=5194 ]
- Description
到冬天了, 这意味着下雪了! 从农舍到牛棚的路上有 N 块地砖, 方便起见编号为 1...N, 第 i 块地砖上积了 fi 英尺的雪
. 在 Farmer John 的农舍的地窖中, 总共有 B 双靴子, 编号为 1...B. 其中某些比另一些结实, 某些比另一些轻便. 具
体地说, 第 i 双靴子能够让 FJ 在至多 si 英尺深的积雪中行走, 能够让 FJ 每步至多前进 di.Farmer John 从 1 号地砖出
发, 他必须到达 N 号地砖才能叫醒奶牛们. 1 号地砖在农舍的屋檐下, N 号地砖在牛棚的屋檐下, 所以这两块地砖都
没有积雪. 帮助 Farmer John 求出哪些靴子可以帮助他走完这段艰辛的路程.
Input
第一行包含两个空格分隔的整数 N 和 B(1≤N,B≤10^5).
第二行包含 N 个空格分隔的整数; 第 i 个整数为 fi, 即 i 号地砖的积雪深度 (0≤fi≤10^9). 输入保证 f1=fN=0
下面 B 行, 每行包含两个空格分隔的整数. 第 i+2 行的第一个数为 si, 表示第 i 双靴子能够承受的最大积雪深度.
第 i+2 行的第二个数为 di, 表示第 i 双靴子的最大步长. 输入保证 0≤si≤10^9 以及 1≤di≤N-1
Output
输出包含 N 行
第 i 行包含一个整数: 如果 Farmer John 能够穿着第 i 双靴子从 1 号地砖走到 N 号地砖, 为 1, 否则为 0
- Sample Input
- 8 7
- 0 3 8 5 6 9 0 0
- 0 5
- 0 6
- 6 2
- 8 1
- 10 1
- 5 3
- 150 7
- Sample Output
- 0
- 1
- 1
- 0
- 1
- 1
- 1
- HINT
- Source
思路: 一眼就想到这个算法了: 鞋子按照能到达的深度排序, 地砖也是. 因为我们鞋子能踩的深度越大, 那么相邻的地砖越近, 如果当前最远的相邻地砖在走的范围内, 说明 ok. 我们然后每次把可以踩的地砖加进去, 然后 set 维护前驱后继, 再维护一个 set 是相邻地砖距离.
虽然 AC 了, 写完发现自己时间有点久, 看了一下, 其他的做法也是差不多, 只是用线段树来维护的, 把可以踩的地砖看成 1, 否则为 0, 那么就是线段树查询最大连续 0 的个数的常规操作.
- #include<bits/stdc++.h>
- #define rep(i,a,b) for(int i=a;i<=b;i++)
- using namespace std;
- const int maxn=100010;
- int s[maxn],d[maxn],ans[maxn],p[maxn];
- bool cmp(int w,int v){ return s[w]<s[v];}
- multiset<int>Len,Point;
- multiset<int>::iterator it1,it2;
- struct in{
- int s,id;
- friend bool operator<(in w,in v){ return w.s<v.s;}
- }f[maxn];
- int main()
- {
- int N,B; scanf("%d%d",&N,&B);
- rep(i,1,N) scanf("%d",&f[i].s),f[i].id=i;
- sort(f+1,f+N+1);
- rep(i,1,B) scanf("%d%d",&s[i],&d[i]);
- rep(i,1,B) p[i]=i;
- sort(p+1,p+B+1,cmp);
- int head=0;
- Len.insert(N-1); Point.insert(1); Point.insert(N);
- rep(i,1,B){
- int now=p[i];
- while(head<N&&s[now]>=f[head+1].s){
- head++; if(f[head].id==1||f[head].id==N) continue;
- it1=Point.lower_bound(f[head].id); it1--;
- it2=Point.upper_bound(f[head].id);
- Len.insert(*it2-f[head].id); Len.insert(f[head].id-*it1);
- Point.insert(f[head].id);Len.erase(Len.find(*it2-*it1));
- }
- if((*(--Len.end()))<=d[now]) ans[now]=1;
- }
- rep(i,1,B) printf("%d\n",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2846641.html