CF2031D Penchick and Desert Rabbit 题解

题意简述

有 n 棵树，第 i 棵树的高度为 a_i，有一只兔子，并且有如下条件：

• 若 j \lt i 且 a_j \gt a_i，则兔子可以从第 i 棵树跳到第 j 棵树

• 若 j \gt i 且 a_j \lt a_i，则兔子可以从第 i 棵树跳到第 j 棵树

现在求对于所有的 1 \le i \le n，求兔子从第 i 棵树出发所能达到的最大高度。

开始解题！

这个题的思路其实是比较显然的，可以维护前缀最大值和后缀最小值来计算答案。具体实现如下：

定义 pre_i 表示前 i 个数的最大值，即 pre_i = \max(pre_{i - 1}, a_i)，注意需要把 pre_0 设为一个极小的数（比如 LLONG_MIN）。

定义 suf_i 表示从 i 到 n 的最小值，注意需要倒序遍历，则 suf_i = \min(suf_{i + 1}, a_i)，注意需要把 suf_{n + 1} 设为一个极大的数（比如 LLONG_MAX）

那么这样维护有什么好处呢？那么显然，通过维护这些值，不需要担心时序问题，即 j \lt i 或 j \gt i 的条件已经自然满足。然后对于第 i 棵树，在理想状态下，其最小可以跳到 suf_{i + 1}，最大可以跳到 pre_i，那么接下来考虑的就是应该如何跳？

所以应该如何跳呢？定义 ans_i 表示树 i 能跳到的最大高度，为了计算 ans_i，会有两种情况：

• 若 pre_i \gt suf_{i + 1}，此时我们假设 a_x = pre_i, a_y = suf_{i + 1}，那么对于第 i + 1 棵树，一定可以通过 i + 1 \rightarrow y \rightarrow x \rightarrow i 到达第 i + 1 棵树，第 i 棵树也可以通过 i \rightarrow x \rightarrow y \rightarrow i + 1 的顺序到达第 i + 1 棵树，那么我们可以得出任何可以从树 i 到达的树都可以从树 i + 1 到达，反之亦然；因此对于这种情况，ans_i = ans_{i + 1}。

• 反之，即 pre_i \le suf_{i + 1}，那么第 i 棵树无法到达第 i + 1 到第 n 棵树中的任何一棵树，则对于这种情况，ans_i = pre_i。

最后，为了使答案最优，我们从右往左遍历，防止答案错误。

时间复杂度 O(Tn)，代码易得。

code :

#include <bits/stdc++.h>
#define ll long long
#define db double

using namespace std;

ll a[1000005], pre[1000005], suf[1000005], ans[1000005];  

char buf[1 << 21], *p1 = buf, *p2 = buf;

const ll getc() {
    return p1 == p2 && ( p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++;
}

const ll read() {
    ll x = 0, f = 1;

    char ch = getc();

    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1; ch = getc();
    }

    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getc();
    }

    return x * f;
}

const void write(ll x) {
    ll sta[35], top = 0;

    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);

    while (top) putchar(sta[--top] + 48);
}

int main() {
    ll T = read();

    while (T--) {
        ll n = read();

        for (ll i = 1; i <= n; i++) {  
            a[i] = read();
        }

        pre[0] = LLONG_MIN;

        for (ll i = 1; i <= n; i++) {
            pre[i] = max(a[i], pre[i - 1]);
        }

        suf[n + 1] = LLONG_MAX;

        for (ll i = n; i; i--) {
            suf[i] = min(a[i], suf[i + 1]);
        }

        for (ll i = n; i; i--) {  
            if (pre[i] > suf[i + 1]) {
                ans[i] = ans[i + 1];
            } else {
                ans[i] = pre[i];
            }
        }

        for (ll i = 1; i <= n; i++) {
            write(ans[i]), putchar(' ');
        }

        puts("");
    } 

    return 0;  
}

AC record