题意

有一个越打越低的防导弹系统，求一个系统最多能打多少导弹和几个系统能打下全部导弹

思路

几个系统能打下全部导弹看这里

当第 $a_i$ 个导弹过来时，遍历它前面的所有打了导弹，选打下来最多的加 1

代码

#include <bits/stdc++.h>
using namespace std;
int a[1005],f[1005],idx,cnt,t,dp[1005],mx;
int n;
bool pd(){
	for (int i = 1;i <= n;i++){
		if (!f[i])	return 1;
	}
	return 0;
}
int main(int argc, char **argv){
	while (cin >> a[++idx])	n++;
	while (pd()){
		t = 30001;
		for(int i = 1;i <= n;i++){
			if (!f[i]){
				if (a[i] <= t){
					t = a[i];
					f[i] = 1;
				}
			}
		}
		cnt++;
	}

	for (int i = 1;i <= n;i++){	// 遍历导弹
		for (int j = 0;j < i;j++){	// 找前面的导弹
			if (a[i] <= a[j])	dp[i] = max(dp[i],dp[j] + 1);
		}
		mx = max(mx,dp[i]);	// 记录打下来最多的
	}
	printf("%d\n%d",mx + 1,cnt);
	return 0;
}

```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,tax1,tax2,h[maxn],f[maxn],is=1;
//第一个大于等于h[i]的位置
int ef1(int l,int r,int s){ 
	while(r-l>1){
        int mid=l+(r-l)/2;
        if(f[mid]>=h[s])l=mid;
		else r=mid;		
    }
    //因为要加入序列，所以返回位置要加一 
    return l+1;
} 
//第一个小于h[i]的位置 
int ef2(int l,int r,int s){
	while(r-l>1){
        int mid=l+(r-l)/2;
        if(f[mid]<h[s])l=mid;
		else r=mid;	
    }
    //因为要加入序列，所以返回位置要加一
    return l+1;
}
int main(){
    while(cin>>h[is]){
    	is++;
	}
	n=is-1;
	f[0]=1e9+7;
	//思路：循环构建不下降序列 ，tax1初始为0 
    for(int i=1;i<=n;++i){
        int l=0,r=tax1+1; 
        int x=ef1(l,r,i);// 查找位置(个数) 
        tax1=max(tax1,x);//更新最大值 
		f[x]=h[i];
    }
    cout<<tax1<<'\n';
	memset(f,0,sizeof(f));
	//思路：循环构建上升序列，tax2初始为0 
    for(int i=1;i<=n;++i){
        int l=0,r=tax2+1;
        int x=ef2(l,r,i);//查找位置(个数) 
        tax2=max(tax2,x);//更新最多值
		f[x]=h[i];
    }
    cout<<tax2;
    return 0;
}

代码:

#include<cstdio>					//scanf / printf
#include<algorithm>					//lower_bound
#include<functional>				//greater_equal
#include<bits/stdc++.h>
using namespace std;
int a,f1[100005],f2[100005],cnt1=-1,cnt2=-1;//f1 存最长上升子序列f2 存最长不上升子序列
int main(){
	while(scanf("%d",&a)==1){//因为导弹个数不确定，所以用while输入
		if(cnt1==-1 || f1[cnt1]<a)f1[++cnt1]=a;//如果序列为空 or 这个数可以直接放在f1末尾,直接插入
		else *lower_bound(f1,f1+cnt1+1,a)=a;//否则替换掉 lower_bound 的位置的数
		if(cnt2==-1||f2[cnt2]>=a)f2[++cnt2]=a;//如果序列为空 or 这个数可以直接放在f2末尾,直接插入
		else *lower_bound(f2,f2+cnt2+1,a,greater_equal<int>())=a;//否则，替换掉 lower_bound 的位置的数 
		//因为 f2 逆序，所以需要传一个 cmp
		//cmp的第二个参数为 lower_bound 待查找值
		//此时 lower_bound 返回第一个 cmp(a,b)==false 的位置
		//greater_equal 为 >=的仿函数形式(cmp)
		//如果是正常函数就不用加括号
	}
	cout<<cnt2+1<<endl<<cnt1+1;
	return 0;	//结束！
}

lower_bound 与 upper_bound 详解与示例:

基本概念:

lower_bound 和 upper_bound 是 C++ 标准库中的算法（定义在 头文件中），用于在‌有序序列‌中快速查找元素的边界位置。它们基于二分查找实现，时间复杂度为 ‌O(log n)‌。

函数定义与参数:

// lower_bound: 返回第一个 >= val 的元素位置
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& val);

// upper_bound: 返回第一个 > val 的元素位置
template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& val);

参数：

first, last: 定义搜索范围的迭代器区间 [first, last)。

val: 要查找的目标值。

可选的第四个参数 comp: 自定义比较函数（如降序序列）。

返回值‌：

指向目标位置的迭代器。若序列中所有元素均小于 val（对于 lower_bound）或小于等于 val（对于 upper_bound），则返回 last。

函数：          返回						示例序列 [1,2,3,3,5] 查找 3
lower_bound 	第一个 ‌≥‌ val 的元素位置 	指向第一个 3（索引 2）
upper_bound 	第一个 ‌>‌ val 的元素位置 	指向 5（索引 4）

示例：

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 3, 5};
    int val = 3;

    // lower_bound 查找第一个 >= val 的元素
    auto lb = std::lower_bound(v.begin(), v.end(), val);
    std::cout << "lower_bound at index: " << (lb - v.begin()) << std::endl; // 输出 2

    // upper_bound 查找第一个 > val 的元素
    auto ub = std::upper_bound(v.begin(), v.end(), val);
    std::cout << "upper_bound at index: " << (ub - v.begin()) << std::endl; // 输出 4

    // 计算 val 的出现次数：upper_bound - lower_bound
    int count = ub - lb;
    std::cout << "Number of " << val << ": " << count << std::endl; // 输出 2

    return 0;
}

来一发 $O(n \space log \space n)$的

可过洛谷加强版数据

洛谷传送门

#include<cstdio>					//scanf / printf
#include<algorithm>					//lower_bound
#include<functional>				//greater_equal
#define N (int)(1e5+1)

using namespace std;

int a,f1[N],f2[N],cnt1=-1,cnt2=-1;	//f1 存最长上升子序列，f2 存最长不上升子序列

int main()
{
	while(scanf("%d",&a)==1)		//因为导弹个数不确定，所以用while输入
	{
		if(cnt1==-1 || f1[cnt1]<a)	//如果序列为空 or 这个数可以直接放在 f1 末尾
			f1[++cnt1]=a;			//直接插入
		else
			*lower_bound(f1,f1+cnt1+1,a)=a;	//否则，替换掉 lower_bound 的位置的数 
		
		if(cnt2==-1 || f2[cnt2]>=a)	//如果序列为空 or 这个数可以直接放在 f2 末尾
			f2[++cnt2]=a;			//直接插入
		else
			*lower_bound(f2,f2+cnt2+1,a,greater_equal<int>())=a;//否则，替换掉 lower_bound 的位置的数 
																//因为 f2 逆序，所以需要传一个 cmp
																//cmp的第二个参数为 lower_bound 待查找值
																//此时 lower_bound 返回第一个 cmp(a,b)==false 的位置
																//greater_equal 为 >=的仿函数形式
																//如果是正常函数就不用加括号
	}
	
	printf("%d\n%d",cnt2+1,cnt1+1);	//输出
	
	return 0;	//结束！
}

附：

【C++】 详解 lower_bound 和 upper_bound 函数

题意

求两个数

• 导弹能打中多少个

• 最少配备多少个导弹

思路

等价于最长上升子序列和最长下降子序列,不信的话,你算一算

优化方法

单调栈(点我查看,知乎的)

单调栈(点我查看,摘要在博客)

代码

#include<iostream>
using namespace std;
int n;
int a[114514];
int dp1[114514],dp2[114514];//两种不同的情况
int main()
{
	int n=0;
	while(cin>>a[n])//连续输入
	{
		n++;
		dp1[n]=1;
		dp2[n]=1;
	}
	dp1[0]=1;
	dp2[0]=1;
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(a[j]>a[i])//最长下降子序列
			{
				dp1[i]=max(dp1[i],dp1[j]+1);
			}
			if(a[j]<a[i])//最长上升子序列
			{
				dp2[i]=max(dp2[i],dp2[j]+1);
			}
		}
	}
	int ma=0;
	for(int i=0;i<n;i++)
	{
		ma=max(ma,dp1[i]);//取最大值
	}
	cout<<ma;//输出
	ma=0;//记得重置
	for(int i=0;i<n;i++)
	{
		ma=max(ma,dp2[i]);//取最大值
	}
	cout<<endl<<ma;//输出
	return 0;//完结散花
}

#include<iostream>
using namespace std;
int main(){
	int n=1,maxn=0,sum=1;
	int arr1[1010]={},arr2[1010]={},k[1010]={};
	arr2[1]=1;
	while(cin>>arr1[n++]);
	if(n==2){
		cout<<0<<endl<<0;//如果没有导弹就输出两个零 
		return 0;
	} 
	for(int i=1;i<=n;i++)k[i]=300010;
	for(int i=2;i<n;i++){
		arr2[i]=1;
		for(int j=i-1;j>=1;j--){
			if(arr1[i]<=arr1[j]&&arr2[i]<arr2[j]+1)arr2[i]=arr2[j]+1;//用动态规划求第一小问（最长不上升子序列） 
		}
		if(arr2[i]>maxn)maxn=arr2[i];
	}
	k[1]=arr1[1];
	for(int i=2;i<n;i++){
		int min=300011,u=1,s=0;
		for(int j=1;j<=sum;j++){
			if(k[j]-arr1[i]<=min&&k[j]-arr1[i]>=0){
				min=k[j]-arr1[i];//用贪心求第二小问（每次都让能拦住这颗导弹中的系统中最小的去拦截） 
				s=j;
				u=0;
			}
		}
		if(u==1){
		    k[++sum]=arr1[i];//如果没有能拦住的系统就增加一颗导弹 
		}
		else k[s]=arr1[i];
	}
	cout<<maxn-1<<endl;
	cout<<sum;
}

#include<bits/stdc++.h>
using namespace std;
int a[10000000];
int f[10000000];
int main(){
	int n=1,maxn=0; 
	while(cin>>a[n]){
		n++;
	}
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=1;j--){
			if(a[j]>=a[i]){
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		maxn=max(maxn,f[i]);
	}
	cout<<maxn<<endl;
	for(int i=1;i<=n;i++){
		f[i]=1;
	}
	maxn=0;
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>=1;j--){
			if(a[j]<a[i]){
				f[i]=max(f[i],f[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++){
		maxn=max(maxn,f[i]);
	}
	cout<<maxn;
}

#include<bits/stdc++.h>
using namespace std;
int a[1005],f[1005],pp[10005],pmax,h,sum=0,k=1;
bool u;
int main(){
	int n=0;
	while(cin>>a[++n]){
		f[n]=1;
		for(int j=1;j<n;j++)if(a[n]<=a[j])f[n]=max(f[n],f[j]+1);
		pmax=max(pmax,f[n]);
	}
	while(k<=n){
		h=a[k++];
		u=false;
		for(int i=1;i<=sum;i++){
			if(pp[i]>=h){
				u=true;
				pp[i]=h;
				break;
			}
		}
		if(!u){
			pp[++sum]=h;
			sort(pp,pp+sum);
		}
	}
	cout<<pmax<<endl<<sum;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int a[1005],f[1005],pp[10005],pmax,h,sum=0,k=1;
bool u;
int main(){
	int n=0;
	while(cin>>a[++n]){
		f[n]=1;
		for(int j=1;j<n;j++)if(a[n]<=a[j])f[n]=max(f[n],f[j]+1);
		pmax=max(pmax,f[n]);
	}
	while(k<=n){
		h=a[k++];
		u=false;
		for(int i=1;i<=sum;i++){
			if(pp[i]>=h){
				u=true;
				pp[i]=h;
				break;
			}
		}
		if(!u){
			pp[++sum]=h;
			sort(pp,pp+sum);
		}
	}
	cout<<pmax<<endl<<sum;
	return 0;
}