题解 导弹拦截

发表于 分类于 阅读次数： Waline： 本文字数： 1.5k

快要 CSP-S2 了，复习一下一些算法（弄文化课弄了好久了，很多东西都要忘了。。。

读题

题目链接: Luogu P1020

数据是这样的：389 207 155 300 299 170 158 65

推一推，我们发现，389 300 299 170 158 65是第一问的答案；在 155->300的时候，要使用另外一颗炮弹了，故最少应该配备两套。

在草稿纸上面推一推，不难发现，这道题的两小问，就是让你求一个不上升序列长度和一个上升序列长度。

预备知识

在求这两个东西之前，需要先学习STL中的两个函数：lower_bound upper_bound。

其中， lower_bound 是求序列中第一个大于等于某个数的数；upper_bound 是求序列中第一个大于某个数的数。这两个函数返回的是指针。

它们使用的前提是 序列是有序的。

以lower_bound为例，具体用法类似：

1
2
3
int a[100];
// ...
lower_bound(a, a+len, x); // 前两个参数传入的都是指针

这一函数默认是求升序序列中符合条件的数，如果要改为降序序列，则需要一个 cmp 函数，这一点类似于 sort。比如：

1
2
3
int a[100];
// ...
lower_bound(a, a+len, x, std::greater<int>()); // 前两个参数传入的都是指针

解题

我的 AC 代码。

本题有两种算法，$O(n)$，$O(nlogn)$。这里只讲后者。

不上升序列

我们用数组d1当作栈来存储它。

遍历导弹高度，把栈顶元素和高度比较：

  1. 若 $a_i <= d_len$，此时$a_i$是符合要求的，直接入栈。
  2. 若 $a_i > d_len$，此时$a_i$把栈内第一个小于它的覆盖掉。这里说一下，能够覆盖它是因为我们不需要再访问它的值了。在测试数据中，此后几次都会进行这一操作，如果仅仅取这几个数据，最长不上升子序列长度仍然正确； 取所有数据，几次操作之后，就会执行操作1，结果仍然正确。

上升序列

和不上升序列一样，只不过把 upper_bound 改为了 lower_bound，因为会出现两个相同高度的导弹的情况，这两个导弹仅仅需要同一的炮弹去拦截。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <algorithm>
#include <iostream>

using namespace std;

int ARR[100001];
int n = 0;
int d1[100001];
int c1 = 0;
int d2[100001];
int c2 = 0;

int main() {
    while (cin >> ARR[n]) n++;
    d1[0] = ARR[0];
    d2[0] = ARR[0];
    for (int i = 1; i < n; i++) {
        if (ARR[i] <= d1[c1])
            d1[++c1] = ARR[i];
        else {
            int j = upper_bound(d1, d1 + c1, ARR[i], greater<int>()) - d1;
            d1[j] = ARR[i];
        }
        if (ARR[i] > d2[c2])
            d2[++c2] = ARR[i];
        else {
            int j = lower_bound(d2, d2 + c2, ARR[i]) - d2;
            d2[j] = ARR[i];
        }
    }
    cout << c1 + 1 << endl << c2 + 1 << endl;
    return 0;
}

结语

能力有限，如有疏漏，请谅解并补充，谢谢。