题目链接：见这里 题意：给了一个串A和一个串B,现在有一个排列，a[]现在你可以在A字符串按照排列删除对应位置上的字符，问你最多可以在哪个位置删除字符使得这个删除之后的字符串还有字串为B，问这个最后的位置。 解法：二分这个最后的，位置然后check就可以了。
//CF 779D#include <bits/stdc++.h>using namespace std;const int maxn = 200005;int n, a[maxn], b[maxn];char s1[maxn], s2[maxn];bool check(int p){ int k = 0; for(int i = p; i < n; i++) b[k++] = a[i]; sort(b, b + k); p = 0; for(int i = 0; i < k; i++){ if(s1[b[i]-1] == s2[p]) p++; } if(p == strlen(s2)) return 1; else return 0;}int main(){ scanf("%s", s1); scanf("%s", s2); n = strlen(s1); for(int i = 0; i < n; i++) scanf("%d", &a[i]); int l = 0, r = n, ans; while(l <= r){ int mid = (l + r) / 2; if(check(mid)) ans = mid, l = mid + 1; else r = mid - 1; } PRintf("%d/n", ans); return 0;}新闻热点
疑难解答
