P1020 导弹拦截

calendar May 7, 2026 · 6 分钟阅读 · 动态规划 最长子序列 二分查找  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1020
难度 绿题（普及+）
知识点 动态规划、最长上升子序列、二分查找
来源 NOIP 1999 提高组

题目描述

某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

已知导弹依次飞来的高度，计算：

  1. 这套系统最多能拦截多少导弹（必须满足后一枚导弹的高度不超过前一枚）
  2. 如果要拦截所有导弹，最少要配备多少套这种导弹拦截系统

输入格式

一行若干个整数，中间由空格隔开，表示导弹依次飞来的高度（以 -1 结束，-1 不算在导弹高度中）

输出格式

两行，每行一个整数：

  • 第一行：一个系统最多拦截的导弹数
  • 第二行：拦截所有导弹最少需要的系统数

解题思路

核心思想

这道题考察的是最长子序列问题：

  1. 第一问：最长不上升子序列（Longest Decreasing Subsequence, LDS）

    • 找到最长的序列，满足后一个元素不大于前一个元素

  2. 第二问：Dilworth 定理

    • 最少不上升子序列覆盖数 = 最长上升子序列长度（Longest Increasing Subsequence, LIS）

算法实现

代码使用二分查找优化，将时间复杂度从 O(n^2) 降到 O(n log n)：

  • d1[] 数组维护最长不上升子序列，使用 upper_bound + greater<int>() 找到插入位置
  • d2[] 数组维护最长上升子序列，使用 lower_bound 找到插入位置

完整代码

C++

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;
int a[N], d1[N], d2[N], n;

// 快速读取整数
inline bool read(int &x) {
    char c = getchar();
    if (c == EOF) return false;
    while (c > '9' || c < '0') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return true;
}

int main() {
    // 读取所有导弹高度
    while (read(a[++n]));
    n--;

    int len1 = 1, len2 = 1;
    d1[1] = d2[1] = a[1];

    for (int i = 2; i <= n; i++) {
        // 处理最长不上升子序列（第一问）
        if (d1[len1] >= a[i]) {
            d1[++len1] = a[i];  // 新增一个元素
        } else {
            // 找到第一个小于 a[i] 的位置替换
            *upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) = a[i];
        }

        // 处理最长上升子序列（第二问）
        if (d2[len2] < a[i]) {
            d2[++len2] = a[i];  // 新增一个元素
        } else {
            // 找到第一个大于等于 a[i] 的位置替换
            *lower_bound(d2 + 1, d2 + 1 + len2, a[i]) = a[i];
        }
    }

    printf("%d\n%d", len1, len2);
    return 0;
}

关键代码讲解

快速读入

inline bool read(int &x) {
    char c = getchar();
    while (c > '9' || c < '0') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return true;
}

使用 getchar() 快速读入整数，比 cin 更快。

最长不上升子序列

if (d1[len1] >= a[i]) {
    d1[++len1] = a[i];
} else {
    *upper_bound(d1 + 1, d1 + 1 + len1, a[i], greater<int>()) = a[i];
}
  • upper_bound 找的是第一个大于 a[i] 的位置
  • 使用 greater<int>() 使其变为找第一个小于 a[i] 的位置
  • 用 a[i] 替换该位置，保持序列最小

最长上升子序列

if (d2[len2] < a[i]) {
    d2[++len2] = a[i];
} else {
    *lower_bound(d2 + 1, d2 + 1 + len2, a[i]) = a[i];
}
  • lower_bound 找的是第一个大于等于 a[i] 的位置
  • 用 a[i] 替换该位置，保持序列最小

示例解析

输入：389 207 155 300 299 170 158 65

步骤 d1 (不上升) d2 (上升)
389 389 389
207 207 207
155 155 155
300 300 155, 300
299 299 155, 299
170 170 155, 170
158 158 155, 158
65 65 65, 158

输出：6（最长不上升子序列长度）2（最长上升子序列长度）

复杂度分析

方法 时间复杂度 空间复杂度
二分查找优化 O(n log n) O(n)

易错点

  1. upper_bound 与 lower_bound 的区别：
    • lower_bound：第一个 大于等于 目标值的位置
    • upper_bound：第一个 大于 目标值的位置
  2. greater<int>() 的作用：使 upper_bound 变为找第一个小于目标值
  3. 初始化：d1[1] = d2[1] = a[1]，长度从 1 开始
  4. 读入结束标志：输入以 -1 结束，但 -1 不算作导弹高度

其他语言解法

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        int[] a = new int[parts.length];
        int n = 0;
        for (String s : parts) {
            int x = Integer.parseInt(s);
            if (x == -1) break;
            a[n++] = x;
        }

        int[] d1 = new int[n + 1];
        int[] d2 = new int[n + 1];
        int len1 = 1, len2 = 1;
        d1[1] = d2[1] = a[0];

        for (int i = 1; i < n; i++) {
            // 最长不上升子序列
            if (d1[len1] >= a[i]) {
                d1[++len1] = a[i];
            } else {
                int l = 1, r = len1, pos = 1;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d1[mid] < a[i]) {
                        pos = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                d1[pos] = a[i];
            }

            // 最长上升子序列
            if (d2[len2] < a[i]) {
                d2[++len2] = a[i];
            } else {
                int l = 1, r = len2, pos = 1;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d2[mid] >= a[i]) {
                        pos = mid;
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                d2[pos] = a[i];
            }
        }

        System.out.println(len1);
        System.out.println(len2);
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    line, _ := in.ReadString('\n')
    parts := strings.Fields(line)

    var a []int
    for _, s := range parts {
        x := 0
        fmt.Sscanf(s, "%d", &x)
        if x == -1 {
            break
        }
        a = append(a, x)
    }

    n := len(a)
    d1 := make([]int, n+1)
    d2 := make([]int, n+1)
    len1, len2 := 1, 1
    d1[1], d2[1] = a[0], a[0]

    for i := 1; i < n; i++ {
        // 最长不上升子序列
        if d1[len1] >= a[i] {
            len1++
            d1[len1] = a[i]
        } else {
            // 二分查找第一个小于 a[i] 的位置
            l, r := 1, len1
            pos := 1
            for l <= r {
                mid := (l + r) >> 1
                if d1[mid] < a[i] {
                    pos = mid
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            }
            d1[pos] = a[i]
        }

        // 最长上升子序列
        if d2[len2] < a[i] {
            len2++
            d2[len2] = a[i]
        } else {
            // 二分查找第一个大于等于 a[i] 的位置
            l, r := 1, len2
            pos := 1
            for l <= r {
                mid := (l + r) >> 1
                if d2[mid] >= a[i] {
                    pos = mid
                    r = mid - 1
                } else {
                    l = mid + 1
                }
            }
            d2[pos] = a[i]
        }
    }

    fmt.Printf("%d\n%d\n", len1, len2)
}

JavaScript

'use strict';

const fs = require('fs');

function main() {
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/).map(Number);
    const a = input.filter(x => x !== -1);

    const d1 = [0]; // 最长不上升子序列
    const d2 = [0]; // 最长上升子序列
    d1.push(a[0]);
    d2.push(a[0]);

    let len1 = 1, len2 = 1;

    for (let i = 1; i < a.length; i++) {
        // 最长不上升子序列
        if (d1[len1] >= a[i]) {
            d1.push(a[i]);
            len1++;
        } else {
            // 二分查找第一个小于 a[i] 的位置
            let l = 1, r = len1, pos = 1;
            while (l <= r) {
                const mid = (l + r) >> 1;
                if (d1[mid] < a[i]) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            d1[pos] = a[i];
        }

        // 最长上升子序列
        if (d2[len2] < a[i]) {
            d2.push(a[i]);
            len2++;
        } else {
            // 二分查找第一个大于等于 a[i] 的位置
            let l = 1, r = len2, pos = 1;
            while (l <= r) {
                const mid = (l + r) >> 1;
                if (d2[mid] >= a[i]) {
                    pos = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            d2[pos] = a[i];
        }
    }

    console.log(len1);
    console.log(len2);
}

main();