P1018 7unar的导弹拦截系统

一.解题思路

1.碎碎念

你怎么知道我又进码蹄杯国赛了🤓👆🏻

————2026.6.17

（如果看完对你有帮助记得点个赞再走呗嘻嘻嘻✨）

2.题目分析

ok，简单过一下题目，题目要求最少需要几套这个系统，而系统要求每一次射击不得高于上一发，所以我们的目标就是找到 最长严格递增子序列 的长度

为什么要这样做呢，我们知道，如果你要打掉这一发导弹，那么你就需要发射与之等高的拦截导弹（为什么不能地面拦截捏🤓👆🏻（雾））

那么接下来这个系统的最大高度就是当前高度了，接下来如果来新的更高的导弹就要添置一套新的系统，而如果来的等于or小于这个的话就用当前系统就行了

我们的lis（最长严格递增子序列）存储的就是每一套系统当前所能发射的最大高度，如果来了比当前高的就安排一个新的系统添进lis并设置成该导弹高度，如果是小于等于就用高度和所在系统中最近的去打它，同时将该系统设置成该导弹高度，这样一直遍历完所有导弹，lis的长度自然就是所需要的最少系统了

理论存在，实践开始！

3.算法实现

想要实现上述过程，我们需要运用耐心排序的思想+贪心and二分算法

首先定义一个数组lis

lis[i]在本题中通俗的含义是这一套系统所能发射的最高拦截导弹

接下来遍历num数组，对每一个x在lis中寻找第一个大于等于它的位置

1.如果没找到，就说明当前系统没有一个能拦住这个导弹，需要添置一套；

2.如果找到了，就将其替换，说明这一套系统拦截了该导弹，并且更新其未来能发射的最大高度

最后输出**lis.size()**即可

4.复杂度

时间：O(nlogn)

空间：O(n)

二.完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin>>n;

    vector<int> num(n);
    for(int i = 0;i<n;++i){
        cin>>num[i];
    }

    vector<int> lis;

    for(auto x:num){
        auto it = lower_bound(lis.begin(),lis.end(),x);
        if(it == lis.end()){
            lis.push_back(x);
        }else{
            *it = x;
        }
    }

    cout<<lis.size()<<'\n';

    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！