最少拦截系统

题目解析

1. 核心思路：贪心策略

为了使用最少的系统，我们的策略应该是：尽量让当前这套系统“物尽其用”。

当一颗新导弹（高度为 $H$ ）飞来时，我们查看当前所有已启动的拦截系统：

如果不止一套系统能拦截它（即系统上一次拦截的高度 $\ge H$ ）：

我们应该选择哪一套？当然是选择那个拦截高度最小，但仍然大于等于 $H$ 的系统。
- 为什么？ 因为高度较高的系统留着去拦截以后可能飞来的较高导弹划算。这就是贪心。
如果没有任何系统能拦截它（所有系统的上一次高度都 $< H$ ）：

没办法，必须新开一套系统，这套系统的当前高度就是 $H$ 。

2. 算法转化 (LIS)

如果你仔细模拟上面的贪心过程，你会发现这等价于在求最长上升子序列 (Longest Increasing Subsequence) 的长度。

我们维护一个数组（例如 tails），其中 tails[i] 并不代表第 $i$ 套系统，而是代表长度为 $i+1$ 的上升子序列的末尾元素的最小值。
对于每一个新来的导弹高度 h：
- 如果在 tails 中找到第一个 $\ge h$ 的数字，我们就用 h 替换它（贪心：降低了该位置的门槛，利于后续延长）。
- 如果 tails 中所有数字都 $< h$ ，说明 h 可以接在最长的序列后面，构成更长的上升子序列，因此将 h 追加到 tails 末尾。
最终 tails 的长度就是答案。

3. 复杂度

朴素贪心/DP： $O(N^2)$ 。
二分优化贪心： 利用 tails 数组的有序性，使用二分查找（std::lower_bound），时间复杂度优化为 $O(N \log N)$ 。这在 $N$ 较大时非常关键。

代码实现 (C++)

假设你习惯使用标准库 (STL) 和流式 I/O，代码如下：

C++

#include <iostream>
#include <vector>
#include <algorithm> // 包含 lower_bound

using namespace std;

// 解决单个测试用例的函数
void solve() {
    int n;
    // 题目指出有若干组数据，第一行为导弹总数
    while (cin >> n) {
        vector<int> missiles(n);
        for (int i = 0; i < n; ++i) {
            cin >> missiles[i];
        }

        // dp数组（或者叫tails数组）
        // 这里 dp[i] 存储的是当前第 i 个拦截系统的“当前拦截能力”（即上一个打掉的导弹高度）
        // 但根据 Dilworth 定理，求“最少不上升子序列覆盖数”等价于求“最长上升子序列长度”
        // 所以这里的逻辑实际上是在构建 LIS
        vector<int> systems;

        for (int h : missiles) {
            // 查找 systems 中第一个大于等于 h 的元素
            // 这意味着我们要找一套现有的系统，它的拦截能力 >= 当前导弹高度
            // 且在所有满足条件的系统中，我们选择拦截能力最弱的（贪心，节省强力系统）
            auto it = lower_bound(systems.begin(), systems.end(), h);

            if (it == systems.end()) {
                // 如果没有找到（说明所有当前系统的拦截能力都小于 h）
                // 或者 systems 为空
                // 我们必须新开一套系统来拦截高度为 h 的导弹
                systems.push_back(h);
            } else {
                // 如果找到了，这就代表这套系统接下了这个导弹
                // 它的拦截能力更新（降低）为 h
                *it = h;
            }
        }

        // 最终系统的数量就是我们需要的最少套数
        cout << systems.size() << endl;
    }
}

int main() {
    // 优化 I/O 速度，养成好习惯
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

关键点解析

while (cin >> n): 处理“若干组数据”的标准写法。
lower_bound: 这是一个二分查找函数。它在有序区间中寻找第一个大于或等于给定值的元素。
- 如果找到了：说明这套系统可以拦截当前导弹，我们更新它的高度（贪心策略：用掉最小的那个足够高的系统）。
- 如果没找到（返回 end()）：说明所有现有系统的高度都比当前导弹低，必须加一套新系统。
等价性: 代码看起来像是在求最长上升子序列（确实也是），但它的物理意义完美对应了“寻找并更新最合适的拦截系统”的过程。

目录

题目解析

1. 核心思路：贪心策略

2. 算法转化 (LIS)

3. 复杂度

代码实现 (C++)

关键点解析