汕头市队赛 SRM 06 A 撕书

A 撕书 SRM 06

背景&&描述

游行寺汀正在杀书。
        书总共有n页，每页都可以看作是一个小写英文字母，所以我们可以把书看成长度为n的字符串s。
        琉璃静静地在旁边看着。根据他对汀的了解，汀+1s只会撕一页。令表示第i秒撕的是哪一页，显然是1..n的一个排列。
        琉璃突然对s的一个非空子序列t产生了兴趣。他想知道，最多在汀撕多少页之后，t仍然是剩下的书的某个子序列。

输入格式

第一行一个字符串，表示s

第二行一个字符串，表示t

第三行n个整数（n为s的长度），表示。

输出格式

一个整数，表示最多在汀撕多少页之后，t仍然是剩下的书的某个子序列。

样例输入

sbkitssakitsak

kisaki

1 14 13 2 6 12 9 10 5 3 8 4 7 11

样例输出

6

数据范围与约定

• 对于100%的数据:

样例解释

6s后，剩下的书为kitsakit，此时kisaki还是书的子序列。第7s撕掉第二个k后就不是了。

查找最大最小的 我一般都会先考虑二分 果不其然这道题就是了 nlogn 完全可做

我们可以记录每个点的消失（也就是被撕）的时间

二分时间求每次是否能匹配就可以了 2333

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=2e5+;

char T[M],s[M];

int n,m,l,r,w[M];

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int check(int k){

    int cnt=;

    for(int i=;i<=n;i++){

        if(w[i]<=k) continue;

        if(T[i]==s[cnt]) cnt++;

        if(cnt==m+) return ;

    }

    return ;

}

int main()

{

    scanf("%s %s",T+,s+);

    int k;

    n=strlen(T+); m=strlen(s+);

    for(int i=;i<=n;i++) k=read(),w[k]=i;

    l=; r=n;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)) l=mid+;

        else r=mid-;

    }

    printf("%d\n",r);

    return ;

}