题目
拦截导弹
贪心、二分
思路
这是一道求最长XX子序列的经典问题,其中XX表示【上升、下降、不上升、不下降】。
题目有两个问题,第一个问题很直接,就是求最长不上升子序列长度,但是第二个问题需要思考,要用到数学定理,不过为了简化问题,这里直接给出结论:第二问就是问最长上升子序列长度。
可以知道的是,求这类最长XX子序列的方法应该是相通的,可以互相转化。所以这里只记录求最长上升子序列长度的方法。
求最长上升子序列长度的方法有很多,动态规划理论上可行,但是时间复杂度为 O ( n 2 ) O(n^2) O(n2),在此题的 100000 100000 100000 的数据范围内显然不可行。然后有更优的解法:贪心+二分。这种方法的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn),可以解决此题,本文记录的也是这种方法。
如何贪心+二分呢?这里直接给出算法。
- 记原数组为 a a a,设置一个辅助数组 b b b,初始化为正无穷
- 从左往右遍历数组 a a a,并对每一个元素 a [ i ] a[i] a[i],使用二分法找出数组 b b b 中第一个大于等于 a [ i ] a[i] a[i] 的下标 t t t,并使 b [ t ] = a [ i ] b[t]=a[i] b[t]=a[i]
- 最后数组 b b b 中不是正无穷的元素个数即为数组 a a a 的最长上升子序列的长度。
其余的最长XX子序列问题也可以触类旁通,这里不再赘述。
代码
#include <limits.h>
#include <stdio.h>
#define N 100005
void init(int* arr, int n) {
for (int i = 0; i < n; i++) {
arr[i] = INT_MAX;
}
}
// 返回数组中第一个大于目标值的下标,没有则返回数组长度
int first_GT(int* arr, int n, int target) {
int l = 0, r = n - 1, mid = 0;
while (l <= r) {
mid = ((r - l) >> 1) + l;
if (arr[mid] > target) {
if (!mid || arr[mid - 1] <= target) {
return mid;
} else {
r = mid - 1;
}
} else {
l = mid + 1;
}
}
return n;
}
// 返回数组中第一个大于等于目标值的下标,没有则返回数组长度
int first_GE(int* arr, int n, int target) {
int l = 0, r = n - 1, mid = 0;
while (l <= r) {
mid = ((r - l) >> 1) + l;
if (arr[mid] >= target) {
if (!mid || arr[mid - 1] < target) {
return mid;
} else {
r = mid - 1;
}
} else {
l = mid + 1;
}
}
return n;
}
int main(void) {
// 读入数据
int a[N], n = 0;
while (~scanf("%d", &a[n])) {
n++;
}
// 建立辅助数组,全部置为最大值
int b[N], i = 0, t = 0, len = 0;
init(b, N);
// 第一问是求最长不上升子序列长度,也就是倒过来的最长不下降子序列长度
// 从右往左找最长不下降子序列
for (i = n - 1; i >= 0; i--) {
// 寻找b中第一个大于a[i]的下标
t = first_GT(b, N, a[i]);
if (t > len) len = t;
// 将这个值替换为a[i]
b[t] = a[i];
}
// 最后输出辅助数组中被更新的值的长度
// 即为题目所求的能拦截导弹的数量
printf("%d\n", len + 1);
// 第二问求的是最长上升子序列长度
// 首先将辅助数组重置
init(b, N);
len = 0;
// 然后从左往右找最长上升子序列
for (i = 0; i < n; i++) {
// 寻找b中第一个大于等于a[i]的下标
t = first_GE(b, N, a[i]);
if (t > len) len = t;
// 将这个值替换为a[i]
b[t] = a[i];
}
// 最后输出辅助数组中被更新的值的长度
// 即为题目所求的需要的最少导弹系统数量
printf("%d\n", len + 1);
return 0;
}
代码是用标准C语言写的,由于C语言并没有提供二分的API,所以只能自己手写,显得代码比较臃肿。其实笔者已经整理好了这类问题的C++模板,见关于O(nlogn)求最长(上升/不上升/下降/不下降)子序列的总结