社区讨论

代码求调,感谢

P1020[NOIP 1999 提高组] 导弹拦截参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lu3y2414
此快照首次捕获于
2024/03/23 18:25
2 年前
此快照最后确认于
2024/03/23 20:05
2 年前
查看原帖
CPP
using namespace std;
#include<bits/stdc++.h>
#define ll long long
const int N=1e5+7;
ll read(){
   ll summ=0;ll f=1;char ch;
   ch=getchar();
   while(ch<'0'||ch>'9'){
	   if(ch=='-'){
		   f=-1;
	   }
	   ch=getchar();
   
   }
   while(ch>='0'&&ch<='9'){
	   summ=summ*10+ch-'0';
	   ch=getchar();
   
   }
   return f*summ;

}
int n=1;
int ar[N];
int f1[N];
int f2[N];    
int main(){
	while(cin>>ar[n]){
        n++; 
    }
    n--;
//	cout<<ar[1]; 
//	for(int i=1;i<=n;i++){
//		f1[i]=1;
//	} 
	int len1=1;
	
	f1[1]=ar[1];
	for(int i=2;i<=n;i++){
		if(f1[len1]>=ar[i]){
			len1++;
			f1[len1]=ar[i];
		}else{
			f1[lower_bound(f1+1,f1+1+len1,ar[i],greater< int >())-f1 ]=ar[i];
		}
		
	}
	cout<<len1<<endl;
	ll len2=1;
	f2[1]=ar[1];
	for(int i=2;i<=n;i++){
		if(f2[len2]<ar[i]){
			len2++;
			f2[len2]=ar[i];
		}else{
			f2[lower_bound(f2+1,f2+1+len2,ar[i])-f2]=ar[i];
		}
	} 
	cout<<len2;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...