题解 P1020 【导弹拦截】

Porsche · 2019-01-29 15:25:15 · 题解

一种不用重载运算符的做法哇咔咔~ 就是把数据变成负的，然后再进行处理，其他思路都一样，不懂的话就看代码吧

#include<bits/stdc++.h>
using namespace std;
int a[100005],f[100005],dp[100005];
int main()
{
    int n=1;
    while(cin>>a[n])n++;
    n--;
    int ans2=1,ans1=1;
    dp[1]-=f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(dp[ans1]<=-a[i])dp[++ans1]=-a[i];
        else dp[upper_bound(dp+1,dp+ans1+1,-a[i])-dp]=-a[i];
        if(f[ans2]<a[i])f[++ans2]=a[i];
        else f[lower_bound(f+1,f+ans2+1,a[i])-f]=a[i];
    }
    cout<<ans1<<endl<<ans2;
    return 0;
}