文章目录
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是 \le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
原题连接：洛谷P1020
输入格式
1行，若干个整数（个数 ≤100000）
输出格式
2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
代码
代码如下（示例）：
#include<bits/stdc++.h>
using namespace std;
int len1=1,len2=1,a[100005],d1[100005],d2[100005];
int main()
{
int n,k=1;
while(~scanf("%d",&n))
{
a[k]=n;
k++;
}
d1[1]=a[1];
d2[1]=a[1];
for(int i=2;i<k;i++)
{
if(d1[len1]>=a[i]) d1[++len1] = a[i];
else
{
int l1 = upper_bound(d1+1,d1+1+len1,a[i],greater<int>())-d1;
d1[l1] = a[i];
}
if(d2[len2]<a[i]) d2[++len2] = a[i];
else
{
int l2 = lower_bound(d2+1,d2+1+len2,a[i])-d2;
d2[l2] = a[i];
}
}
cout<<len1<<endl<<len2<<endl;
return 0;
}
总结
greater<:int>是c++提供的大于函数，用于下降序列
lower_bound会找出序列中第一个大于等于x的数
upper_bound会找出序列中第一个大于x的数