只得了30分,求助大佬

P1439 【模板】最长公共子序列

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。

因为如果用结构体排了序,就会影响到原序列的大小关系。


|