题解：P15017 [UOI 2020 II Stage] 大炮

s23261 · 2026-01-25 14:46:53 · 题解

来一个线段树的做法。

题目大意

哥萨克从第 1 段的大炮出发，沿 45 度角向前飞行，直到撞到钟乳石或路径尽头的墙。撞到钟乳石后垂直下落到对应段的前一段，撞到墙则下落到最后一段。重复此过程直到到达最后一段，求发射次数。

碰撞条件：从第 now 段出发，飞行到第 k 段时，若钟乳石高度 a_k 满足 a_k \le k - now，则会撞到钟乳石。

解题思路

转化问题：将碰撞条件转化为 b_k = a_k - k \le -now，其中 b_k 为预处理数组，-now 为当前查询阈值。

线段树查询：构建线段树维护 b 数组区间最小值，高效查询每个 now 对应的第一个满足 b_k <= -now 的位置 k。

模拟跳跃：根据查询结果更新当前位置并统计发射次数，直到到达最后一段。

::::success[AC代码]

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], b[N];
vector<int> tree;
void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = b[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
int query(int node, int nl, int nr, int l, int r, int x) {
    if (nr < l || nl > r) {
        return -1;
    }
    if (tree[node] > x) {
        return -1;
    }
    if (nl == nr) {
        return nl;
    }
    int mid = (nl + nr) / 2;
    int res = query(2 * node, nl, mid, l, r, x);
    if (res != -1) {
        return res;
    }
    return query(2 * node + 1, mid + 1, nr, l, r, x);
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i] - i;
    }
    int trlen = 1;
    while (trlen < n) {
        trlen <<= 1;
    }
    tree.assign(2 * trlen, INT_MAX);
    build(1, 1, n);
    int now = 1;
    int ans = 0;
    while (now < n) {
        int x = -now;
        int k = query(1, 1, n, now + 1, n, x);
        if (k != -1) {
            ans++;
            now = k - 1;
        } else {
            ans++;
            now = n;
        }
    }
    cout << ans << endl;
    return 0;
}

::::