Luogu

算法

大力模拟。

考虑木块最多上移$n$层。

维护一个$Min[i]$，表示前$i$个数的最小值。
容易发现$Min[i]=min(Min[i-1],a[i])$。

那么对于每一个长度为$k$的木块，当$Min[now]<k$，也就是上面有方块能挡住它时，不断上移。

若上移到0了则直接输出0，然后return 0即可。

注意$a[0]$和$Min[0]$一开始要置成$+\infty$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[300010];
int Min[300010];

int main() {
    int n=read(),m=read();
    a[0]=Min[0]=0x7f7f7f7f;
    for (re int i=1;i<=n;i++) a[i]=read(),Min[i]=min(Min[i-1],a[i]);
    
    int now=n+1;
    for (re int i=1;i<=m;i++) {
        int k=read();
        do { now--; } while (Min[now]<k);
        if (!now) { printf("0\n"); return 0; }
    }
    
    printf("%d\n",now);
    return 0;
}
最后修改：2019 年 05 月 26 日 02 : 35 PM
© 允许规范转载