怪盗基德的滑翔翼

题目描述

N 幢高度互异的建筑排成一条线，怪盗基德从任意一幢出发，选定一个方向后中途不能改，每一步只能飞向更低的建筑（可跳过中间）。求起点、方向任选时最多能经过的建筑数（含起点，K<100 组，每组 N<100）。样例输入：3 / 8 / 300 207 155 299 298 170 158 65 / 8 / 65 158 170 298 299 155 207 300 / 10 / 2 1 3 4 5 6 7 8 9 10，输出：6 6 9。

思路

方向不能改，左右各算一次后取较大值；高度只能下降，把高度取反就变成标准 LIS——tails[L] 记长度为 L 的上升子序列的最小结尾（严格递增），每个值二分定位：能接就追加，否则替换同长度结尾，单点 O(N log N)。

参考代码

Python 版：

python

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
34
35
36
37
38
39
40
41
42
43
44
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:27
# update_at: 2026-09-30 03:27

import sys
from bisect import bisect_left


def lis_length(seq: list[int]) -> int:
    """严格上升子序列的最大长度：tails[L-1] 是长度 L 的子序列的最小可能结尾。"""
    tails: list[int] = []
    for value in seq:
        pos = bisect_left(tails, value)  # 第一个 >= value 的位置，也就是该值能顶替的最短长度
        if pos == len(tails):
            tails.append(value)          # 比所有层的结尾都大，可以再加一层
        else:
            tails[pos] = value           # 同长度换成更小的结尾，后续更容易接上
    return len(tails)


def best_glide(heights: list[int]) -> int:
    """一次单向滑翔最多经过的建筑数：起点任选、方向任选，但只能飞向更低的建筑。"""
    rightward = [-h for h in heights]                 # 向右滑：下标递增而高度递减，取负变递增
    leftward = [-h for h in reversed(heights)]        # 向左滑：时间倒放，等价于反转序列后同法计算
    return max(map(lis_length, (rightward, leftward)))  # 两个方向互相独立，取更优者


def solve() -> None:
    it = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    case_count = next(it)                # 题面的 K
    for _ in range(case_count):
        building_count = next(it)        # 题面的 N
        heights = [next(it) for _ in range(building_count)]
        out.append(str(best_glide(heights)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:03
 * update_at: 2026-10-05 08:03
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;

int n;                    // 当前组测试数据的建筑数量
int h[MAXN];              // 建筑高度序列，下标从 1 开始
int key[MAXN];            // key[i] = -h[i]，把"下降"翻成"上升"
int tails[MAXN];          // tails[L-1] 是长度为 L 的上升子序列的最小结尾；序列严格递增

// 在 tails[0..len-1] 上二分：找到第一个 >= value 的位置 p。
// p == len 表示 value 比所有层结尾都大，可以再接一层；
// 否则 p 是 value 顶替的位置，让同长度留出更小的结尾。
int lower_bound_pos(int len, int value) {
    int l = 0, r = len; // [l, r) 半开区间
    while (l < r) {
        int mid = (l + r) / 2;
        if (tails[mid] < value) l = mid + 1;
        else r = mid;
    }
    return l;
}

// 求 seq[1..len] 上严格上升子序列的最大长度；调用前 seq 已是准备好的序列
int lis_length(int len) {
    int sz = 0; // 当前 tails 的有效长度
    for (int i = 1; i <= len; i++) {
        int p = lower_bound_pos(sz, key[i]);
        if (p == sz) {
            tails[sz] = key[i]; // 追加一层
        } else {
            tails[p] = key[i];   // 顶替同长度的结尾
        }
        sz = (p == sz) ? sz + 1 : sz;
    }
    return sz;
}

// 一次单向滑翔最多经过的建筑数；方向任选、起点任选，但只能飞向更低的建筑
int best_glide(int len) {
    // 向右滑：下标递增、高度递减 → 取负后变成严格上升子序列
    for (int i = 1; i <= len; i++) key[i] = -h[i];
    int right_ans = lis_length(len);

    // 向左滑：把序列反转，等价于反转序列的向右滑
    for (int i = 1; i <= len; i++) key[i] = -h[len - i + 1];
    int left_ans = lis_length(len);

    return right_ans > left_ans ? right_ans : left_ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k; // 测试数据组数
    cin >> k;
    while (k--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> h[i];
        cout << best_glide(n) << "\n";
    }

    return 0;
}

怪盗基德的滑翔翼

目录

题目描述

思路

参考代码