题解 | 拦截导弹

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

// 严格递增 LIS
int LIS_strict(const vector<int>& a) {
    vector<int> tail;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x); // 第一个 >= x
        if (it == tail.end()) tail.push_back(x);
        else *it = x;
    }
    return (int)tail.size();
}

// 非增 LNIS ：等价于对 -a 求“非降”LNDS（用 upper_bound）
int LNIS(const vector<int>& a) {
    vector<int> tail; // 存放 -a 的最小结尾
    for (int x : a) {
        int y = -x;
        auto it = upper_bound(tail.begin(), tail.end(), y); // 第一个 > y
        if (it == tail.end()) tail.push_back(y);
        else *it = y;
    }
    return (int)tail.size();
}

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

    cout << LNIS(h) << '\n'          // 一套系统最多拦截
         << LIS_strict(h) << '\n';   // 最少需要的系统数
    return 0;
}