你的二分写错了,如果l = mid+1,r = mid-1的话,条件应该是l<=r,而且应该是q[l] = sou[nor[i]]
by az__eg @ 2022-07-15 20:25:14
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2000001;
int n,nor[N],sou[2000001],f[N],q[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>nor[i];
cin>>sou[nor[i]];//表示nor[i]对应的友好城市
}
sort(1+nor,1+n+nor);
// cout<<endl;
// for(int i=1;i<=n;i++){
// cout<<nor[i]<<" "<<sou[nor[i]]<<endl;
// }
/*for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(sou[nor[i]]>sou[nor[j]]){
// cout<<123;
f[i]=f[j]+1;
}
}
f[i]=max(f[i],1);
}
int maxn=-1;
for(int i=1;i<=n;i++){
maxn=max(maxn,f[i]);
// cout<<f[i]<<" ";
}
cout<<maxn;//DP解法O(n^2)*/
//P2:二分
int l=1,r=n,k=0;
for(int i=1;i<=n;i++){
if(sou[nor[i]]>q[k]){//入队
k++;
q[k]=sou[nor[i]];
}
else{
l=1,r=k;
int mid = 0;
while(l<=r){
mid=(l+r)/2;
if(sou[nor[i]]>q[mid]){
l=mid+1;
}
else {
r=mid-1;
}
}
q[l]=sou[nor[i]];
}
}
cout<<k;
}
```
by az__eg @ 2022-07-15 20:25:31
@[wangziang](/user/283894)
by az__eg @ 2022-07-15 20:29:31
@[mmdxm](/user/229801)
过了,感谢
by Ang_QwQ @ 2022-07-16 10:03:34