[USACO2018FEB]Snow Boots G

题面传送门

作为一名noip省一都拿不到的蒟蒻,当然肯定先想暴力:

复杂度O(N*B) :

枚举每一个靴子,再扫一遍雪地,看看不能走的块(我们这里把它称作黑块)最长连续有多长,如果小于等于当前靴子的最大长度,那么当然是可以过去了。

然后好像有优化?

因为我们靴子之间是没有制约关系的,我们可以把靴子从大到小排序,因为这样的话,前一个靴子不能走的块,后面一个靴子也不能走,这样就会使得黑块的数量是单调上升的。

所以我们这样就O(N)扫一遍雪地就行了,但是雪地是无序的,处理起来还是很麻烦,因为被扫过的块有可能能使第i个靴子过,但不能使第$i+1$个靴子过,我们就得再扫一遍雪地。复杂度又爆炸了。

例如:

$hi$=10,$h_{i+1}$=11;

$si$=10,$s_{i+1}$=9;

扫到$si$时我们扫过hi不标黑,扫到$h_{i+1}$把这个块代表的位置标黑了。 然后我们扫$s_{i+1}$时,只能到$h_{i+2}$个雪地了。而对于$s_{i+1}$这个靴子来说,hi也应该是黑的,但我们无法再扫到$hi$了,所以对于这个$s_{i+1}$个靴子来说黑格子多了一个.

所以我们要把靴子和雪地都从大到小排序,然后从大到小枚举靴子和雪地即可.

然后这个时候我们还需要一个链表,我们把n个雪地搞成一个链表,初始每个雪地有一个左指针和右指针,分别指向左边第一个和右边第一个。

然后每次当h[j]>s[i]时,我们就把它在链表中所在的那个位置删除。

但怎么删除呢?

如果我们把当前元素的左指针的右指针指向当前元素的右指针,并且把当前元素的右指针的左指针指向当元素的左指针,那么我们是不是就相当于在链表中跳过了这个元素,就实现了删除操作。

然后统计答案就是链表中所有存在元素的(右指针-左指针)取max即可。

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<set>
#define N 120000
#define ri register int
using namespace std;
template <class T> void in(T &x) {
    x=0;
    bool flag=0;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    if(flag)
        x=-x;
}
int l[N],r[N];
int h[N],n,m,vis[N],ans[N],maxm=-1;
struct node {
    int s,step,id;
} a[N];
struct snow {
    int h,id;
} sn[N];
inline bool cmp(node x,node y) {
    return x.s>y.s;
}
inline bool cmpp(snow x,snow y) {
    return x.h>y.h;
}
int main() {
    in(n),in(m);
    for(ri i=1; i<=n; ++i)in(sn[i].h),sn[i].id=i;
    for(ri i=1; i<=m; ++i)in(a[i].s),in(a[i].step),a[i].id=i;
    sort(sn+1,sn+n+1,cmpp);
    sort(a+1,a+m+1,cmp);
    for(ri i=1; i<=n; ++i)
        l[i]=i-1,r[i]=i+1;
    int j=1;
    for(ri i=1; i<=m; ++i) {
        while(j<=n&&sn[j].h>a[i].s) {
            r[l[sn[j].id]]=r[sn[j].id];
            l[r[sn[j].id]]=l[sn[j].id];
            //  printf("%d %d %d\n",j,l[j],r[j]);
            maxm=max(maxm,(r[sn[j].id]-l[sn[j].id]));
            ++j;
        }
        ans[a[i].id]=(a[i].step>=maxm);
    }
    for(ri i=1; i<=m; ++i)
        printf("%d\n",ans[i]);
}

发表于 2018-09-20 17:51:32 in 题目