chenwanxi41 @ 2018-08-22 10:41:27
#include<algorithm>
#include<cstring>
using namespace std;
int read()//读入优化
{
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
int h=0;
while(ch<='9'&&ch>='0')
{
h=h*10+ch-48;
ch=getchar();
}
return h;
}
struct node//结构体,a.x存储第一个数组,a.y存储第二个数组
{
int x,y;
};node a[1000100];
int f[1010001];
bool cmp(node m,node n)
{
return m.x<n.x;
}
int main()
{
int n,j=-1,sum=0,len=0;//len通过记录f数组的有效位数,求得个数
n=read();
memset(f,0x7f,sizeof(f));f[0]=0;//初始化
for (int i=1;i<=n;i++) a[i].x=read();
for (int i=1;i<=n;i++) a[i].y=read();
sort(a+1,a+1+n,cmp);//排序
for (int i=1;i<=n;i++)
{
int l=0,r=len,mid;
if (a[i].y>f[len]) f[++len]=a[i].y;//如果刚好大于末尾,暂时向后顺次填充
else
{
while (l<r)
{
mid=(l+r)/2;
if (f[mid]>a[i].y) r=mid;
//如果仍然小于之前所记录的最小末尾,那么不断向前寻找(因为是最长上升子序列,所以f数组必然满足单调)
else l=mid+1;
}
f[l]=min(f[l],a[i].y);//更新最小末尾
}
}
printf("%d",len);
return 0;
}```
为方便读懂,解释说明有的是从题解里抄来,请见谅
by 醉语梦 @ 2018-08-22 11:17:41
不能用sort做
for (int i=1;i<=n;i++) idx[read()]=i;
for (int i=1;i<=n;i++) a[i].y=id[read()];
这样试试
by Brave_Cattle @ 2018-10-05 21:32:17
用结构体排序是会出现问题的。下面有一组hack数据:
3
3 1 2
2 1 3
如果排序了,算出来的结果就是2。
因为如果用结构体排了序,就会影响到原序列的大小关系。