【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;
}