拦截导弹

拦截导弹【贪心 + 二分】 / 【dp】

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例

389 207 155 300 299 170 158 65

6
2

提示

对于前$50\%$数据（NOIP 原题数据），满足导弹的个数不超过$10^4$个。该部分数据总分共$100$分。可使用$\mathcal O(n^2)$做法通过。
对于后$50\%$的数据，满足导弹的个数不超过$10^5$个。该部分数据总分也为$100$分。请使用$\mathcal O(n\log n)$做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过$5\times 10^4$。

此外本题开启 $spj$ ，每点两问，按问给分。

NOIP1999 提高组 第一题

---

$\text{upd 2022.8.24}$：新增加一组 Hack 数据。

思路

贪心+二分为正解，$dp$ 复杂度为$\mathcal O(n^2)$，会超时。

$Dilworth$ 定理

• 把序列分成不升子序列的最少个数，等于序列的最长上升子序列长度
• 把序列分成不降子序列的最少个数，等于序列的最长下降子序列长度

题目简化：

给定一个数列 $b$，问：

1. 它的最长不上升子序列长度；
2. 最少能被划分成多少个不上升子序列。

数组 $b$ 存储从输入数据；
数组 $l$ 存储最长不上升子序列；
变量 $r_1$ 代表 $l$ 的结尾位置（即最长不上升子序列的长度）。

把 $b$ 中的每个元素挨个放到 $l$ 里：

• 如果 $b_i\leq l_{r_1}$,说明 $b_i$ 可以直接加入 $l$（而整个 $l$ 数组还是有序的）；
• 如果 $b_i> l_{r_1}$，说明若放入 b_i 则 $l$ 会无序，所以要找办法把 $b_i$ 放进去：

怎么放呢？在 $l$ 中找到第一个小于 $b_i$ 的数，用 $b_i$ 代替它。
找到第一个小于 b_i 的数，使用 upper_bound 可以在$\mathcal O(n\log n)$复杂度内找到（需要改比较器）。

由于它返回的是指针就可以有一些奇特操作。

*upper_bound(l + 1, l + r1 + 1, b[i], greater<int>()) = b[i];
*upper_bound(all(l), b[i], greater<int>()) = b[i];

CODE

void solve()
{
    int x;
    vector<int> v;
    while (cin >> x)    v.push_back(x);
    vector<int> a, b;
    for (auto x : v)
    {
        auto it = lower_bound(all(a), x);
        if (it != a.end())  *it = x;
        else    a.push_back(x);
    }
    for (auto x : v)
    {
        auto it = upper_bound(all(b), x, greater<int>());
        if (it != b.end())  *it = x;
        else    b.push_back(x);
    }
    cout << b.size() << _endl << a.size();
}