「题解」「POI2016」KRA-The Disks

题目链接:Luogu P3434/BZOJ 1510/POI 2016。

未完待续

题解

思路

用数组 Min[] 表示前缀最小值,则我们只需要对此进行判断即可。

代码

该程序的渐进时间复杂度为 $\Theta(n)$ 。

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::min;
#define reg register
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //读入优化
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}
const int MAXN=300000+5;
const int MAXM=300000+5;
int n,m;
int r[MAXN],k[MAXM];
int Min[MAXN];
int main(void){
    reg int i,pos;
    pos=n=read(),m=read();
    memset(Min,0X3F,sizeof(Min)); //初始化
    for(i=1;i<=n;++i)
        r[i]=read();
    for(i=1;i<=m;++i)
        k[i]=read();
    for(i=2;i<=n;++i)
        Min[i]=min(Min[i-1],r[i]);
    for(i=1;i<=m;++i){
        while(Min[pos]<k[i])
            --pos;
        --pos;
        if(!pos)
            return puts("0"),0;
    }
    printf("%d\n",pos+1); //输出答案
    return 0;
}