Back

导弹拦截

hilaolu

hilaolu

November 21, 2017
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000001];
int c[1000001];
int main(){
    int n=0,len=1,p,len1=1,tmp;
    while(cin>>tmp){
          a[n]=tmp;
          n++;
    }
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    c[1]=a[0];
    for(int i=1;i<n;i++){
        if(a[i]>c[len]){
            len++;
            c[len]=a[i];
        }else{
            p=lower_bound(c+1,c+len+1,a[i])-c;
            c[p]=a[i];
        }
    }
    for(int i=0;i<n;i++)c[i]=0;
    c[1]=a[0];
    for(int i=1;i<n;i++){
        if(a[i]<=c[len1]){
              len1++;
              c[len1]=a[i];
        }else{
              p=upper_bound(c+1,c+len1+1,a[i],greater<int>())-c;
              c[p]=a[i];
        }
    }
    cout<<len1<<endl<<len;
    return 0;
}

关键是坑爹的upper_bound的用法。在反序区间要加greater<int>()来实现重载。

Comment has been closed