30分，求大佬查错

Phoenix030821 @ 2018-02-11 12:43:40

#include<bits/stdc++.h>
using namespace std;
struct lis{
    int p1,p2;
}a[100001];
bool cmp(lis m,lis n){
    return m.p1<n.p1;
}
int main(){
    int n;
    cin>>n;
    for(int x=1;x<=n;x++)cin>>a[x].p1;
    for(int x=1;x<=n;x++)cin>>a[x].p2;
    sort(a+1,a+n+1,cmp);
    int g[n+5],maxa=1;
    memset(g,0,sizeof(g));g[1]=a[1].p2;
    for(int x=2;x<=n;x++){
        if(a[x].p2>g[maxa])maxa++,g[maxa]=a[x].p2;
        else{
            int low=1,high=maxa+1;
            while(low<high){
                int mid=(low+high)>>1;
                if(a[x].p2<g[mid])high=mid;
                else low=mid+1;
            }
            g[low]=a[x].p2;
        }
        cout<<maxa<<" ";
    }
    cout<<maxa;
    return 0;
}

by chenwanxi41 @ 2018-08-22 10:42:59

我也和你一样的思路，但也只对了三个点

#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;
}```