修正,因为n没有走到最远,所以会出错(样例没有这个问题,所以没发现)
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int a[200003],b[200003],ta=0,ans=0,n,maxx=1000003,maxxx=0;
int read()
{
int x=0,f=1;
char c=getchar();
while(c<48 || c>57)
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>=48 && c<=57)
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int x=read();
if(x>maxxx)
maxxx=x;
a[x]=read();
}
for(int i=1;i<=200001;i++)
b[i]=maxx;
b[0]=0;
for(int i=1;i<=maxxx;i++)
{
if(!a[i])
continue;
for(int j=ans;j>=0;j--)
{
//cout<<b[j]<<" "<<a[i]<<endl;
if(b[j]<a[i])
{
if(j+1>ans)
ans=j+1;
if(b[j+1]>a[i])
b[j+1]=a[i];
break;
}
}
}
cout<<ans;
return 0;
}
```
205ms(未O2)
by chino_33 @ 2021-09-09 13:21:42
@[chino_33](/user/98673) 你这代码时间复杂度是 $O(N^2)$ 的,可以被如下 generator 生成的数据卡掉:
``` cpp
#include<bits/stdc++.h>
using namespace std;
const int max_N=2e5+5;
int p[max_N];
int main()
{
freopen("data.in","w",stdout);
int N=2e5;
p[1]=1;
for(int i=2;i<=N/2;++i)
p[i]=N/2+i;
for(int i=N/2+1;i<=N;++i)
p[i]=i-N/2+1;
printf("%d\n",N);
for(int i=1;i<=N;++i)
printf("%d %d\n",i,p[i]);
return 0;
}
```
~~这题数据也太水了吧,让时间复杂度错误的解法过了也就算了,竟然还是最优解?!~~
by wsyhb @ 2021-09-09 13:30:32
@[wsyhb](/user/145355) 被卡烂了
~~嘛,如果答案ans小一点,就比N²小不少了~~
by chino_33 @ 2021-09-09 13:47:07