社区讨论
代码求调,感谢
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 条回复,欢迎继续交流。
正在加载回复...