社区讨论

各位大佬,二分求救

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 条回复,欢迎继续交流。

正在加载回复...