社区讨论
各位大佬,二分求救
P2782友好城市参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo8kmgom
- 此快照首次捕获于
- 2023/10/27 20:09 2 年前
- 此快照最后确认于
- 2023/10/27 20:09 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=200001;
int n,nor[N],sou[1000001],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;
while(l<r){
mid=(l+r)/2;
if(sou[nor[i]]>q[mid]){
l=mid+1;
}
else {
r=mid-1;
}
}
q[mid]=sou[nor[i]];
}
}
cout<<k;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...