奇怪的问题
查看原帖
奇怪的问题
556740
hzx360楼主2022/9/11 23:45

第22行为什么ans1要减1才能AC(QAQ

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int h[N],f[N],g[N],n;
int main(){
	int ans1=0,ans2=1;
	f[0]=0;
	while(~scanf("%d",&h[++n]));
	for(int k=1;k<=8;k++){cin>>h[k];}
	for(int k=1;k<=n;k++){
		int l=1,r=ans1,o=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(f[mid]>=h[k]) l=mid+1,o=mid;
			else r=mid-1;
		}
		ans1=max(ans1,o+1);
		f[o+1]=max(f[o+1],h[k]);
	}
	cout<<ans1-1<<endl;
	g[1]=h[1];
	for(int k=2;k<=n;k++){
		int l=1,r=ans2,o=0;
		while(l<=r){
			//cout<<l<<" "<<r<<endl;
			int mid=(l+r)/2;
			if(g[mid]>=h[k]) r=mid-1,o=mid;
			else l=mid+1;
		}
		if(o==0) ans2++,g[ans2]=h[k];
		else g[o]=h[k];
	}
	cout<<ans2<<endl;
}
2022/9/11 23:45
加载中...