// 妙
// 通过找出第二个序列B中每个值在第一个序列A中对应的下标,问题转化为求下标数组的最长上升子序列
// 最长上升子序列的nlogn贪心做法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int arr[N];
int b[N];
vector<int> ind;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) //从1开始方便后面判断若在b数组中下标为0是没找到
{
int x;
scanf("%d", &x);
arr[x]=i;
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%d", &x);
b[i]=arr[x];
}
//b[i]中为0的表示仅在B中出现而未在A中找到的数
vector<int> vec;
for(int i=1;i<=n;i++)
{
if(b[i]==0)
{
continue;
//cout<<"我不会执行"<<endl;
}
if(!vec.size() || b[i]>vec.back())
{
vec.push_back(b[i]);
//cout<<"我执行了"<<endl;
}
// int it=lower_bound(vec.begin(),vec.end(),b[i])-vec.begin();
// vec[it]=b[i];
auto it=lower_bound(vec.begin(),vec.end(),b[i]); //这里求出的是迭代器,下面加*之后再取数组是数组内部的值,故错误
*it=b[i];
}
//for(auto it=vec.begin();it!=vec.end();it++) cout<<*it<<' ';
cout<<vec.size();
}
其实stk中存储的并不是顺序的最长子序列,而是stk[i]表示以stk[i]结尾的最长的上升子序列长度为i+1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
int arr[N];
int b[N];
vector<int> vec;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d", &x);
arr[x]=i;
}
for(int i=1;i<=n;i++)
{
int x;
scanf("%d", &x);
b[i]=arr[x];
}
for(int i=1;i<=n;i++)
{
if(b[i]==0) continue;
if(vec.empty()||b[i]>vec.back()) vec.push_back(b[i]);
*lower_bound(vec.begin(),vec.end(),b[i])=b[i];
}
cout<<vec.size();
}