违规用户名59285 @ 2019-08-27 22:48:01
#include<cstdio>
#include<algorithm>
using namespace std;
int N;
int m[100005],a[100005],b[100005];
int l,r,mid;
int k[100005];
int cnt;
const int INF=0x3ffffff;
int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
scanf("%d",&a[i]);
m[a[i]]=i;
}
for(int i=1;i<=N;i++)
{
scanf("%d",&b[i]);
k[i]=INF;
}
k[0]=0;
for(int i=1;i<=N;i++)
{
if(m[b[i]]>k[cnt])
{
cnt++;
k[cnt]=m[b[i]];
}
else
{
l=0;
r=N;
while(l<r)
{
mid=(l+r)>>1;
if(k[mid]<m[b[i]])
l=mid+1;
else
r=mid;
}
k[l]=min(k[l],m[b[i]]);
}
}
printf("%d",cnt);
return 0;
}
//这是ac代码 但去掉正无穷的初始化只有20 k[i]数组记录的是长度为k的lis的最小末尾数,但明明每次与m[b[i]]进行比较的k[cnt]都是之前被更新过的 照理说初始化与否不会造成影响啊 为什么会出错呢
by Smile_Cindy @ 2019-08-27 22:54:27
@江沢铭路
事实证明你的确用到了没被更新过的k[cnt]
虽然我不知道为什么。
by 0nullptr @ 2019-08-27 23:10:44
@江沢铭路
考虑这样的一组数据
5
1 2 3 4 5
5 1 2 3 4
那么有m[]={1,2,3,4,5}
当m[b[i]]>k[cnt]
更新
当m[b[i]]>k[cnt]
。由于
by 违规用户名59285 @ 2019-08-28 17:35:29
@zs__std
噢噢 刚发现我把r=cnt写成r=N 这样的话确实如你所说 会调用到没更新的k 改成r=cnt 删掉初始化能ac 受教了