【ssl】【二分】勇闯黄金十二宫射手宫
题目
解题思路
首先要注意是可不连续的
先用一个数组标记出哥哥的基因出现位置
然后用弟弟的去匹配
存储目前与哥哥能匹配上的位置
如果当前数在哥哥基因中出现的位置比上一次匹配的要后,直接加入
否则找到第一个比ta大的位置,更新
因为能匹配上的基因数量不变,更新位置使队列更优
代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,t,w[1000100],a[1000100],d[100010];
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&x);w[x]=i;}for (int i=1;i<=n;i++)scanf("%d",&a[i]);for (int i=1;i<=n;i++)if (w[a[i]]>d[t])d[++t]=w[a[i]];else {int z=lower_bound(d+1,d+t,w[a[i]])-d; //找到第一个大于等于w[a[i]]d[z]=min(d[z],w[a[i]]); }printf("%d",t);return 0;
}