题目意思是给你一个字符串,然后接下来是一个字串,然后再给你一个原字符串每个字符位置打乱的序列,按照这个序列开始删除字符,直到删除到再删除会导致字串不存在为止,问你最多删除多少次。

竟然是二分!!!虽然开始看到给出的字符串很长,想想也不可能是常规的解法,但是二分实在没想到啊,二分的题做的太少了。

二分,把序列二分一下查找字串是否存在,嗯,就是这么个意思。


代码:

StatusAccepted
Time62ms
Memory4096kB
Length947
LangGNU G++ 5.1.0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <memory.h>
using namespace std;
#define MAX 200005
char t[MAX], p[MAX];
int a[MAX], flag[MAX], lent, lenp, l, r, mid, ans;
int check(int x){
    int tans=0;
    memset(flag, 0, sizeof(flag));
    for(int i=0;i<x;i++)flag[a[i]-1]=1;
    for(int i=0;i<lent;i++){
        if(!flag[i] && t[i]==p[tans])tans++;    //如果还没删除并且为p的字串
        if(tans>=lenp)return 1;                 //如果长度大于字串,即为字串
    }
    return 0;
}
int main()
{
    while(~scanf("%s", t)){
        scanf("%s", p);
        lent = strlen(t);
        lenp = strlen(p);
        for(int i=0;i<lent;i++)scanf("%d", &a[i]);
        l=0;
        r=lent-1;
        ans = 0;
        while(l<=r){
            mid = (l+r)>>1;
            if(check(mid)){     //如果存在字串,继续循环
                l = mid+1;
                ans=mid;
            }
            else r = mid-1;
        }
        printf("%d\n", ans);
    }
    return 0;
}