题解 导弹拦截

快要 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;
}

结语

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