天赐的算法笔记 01 - CF 2123C 前缀最小值与后缀最大值

写在前面

大家好，我是天赐。

最近发生了许多事情，总的来说就是毕业，以及各种由它锁带来的各种其他事。我想找点机会做点改变，在我的生活里找一点掌控感。

于是，我选择记录算法笔记。

虽然 AI 在 Coding 方面的进步总让人怀疑，学习 DSA 以及训练是否依然有必要，但在我看来，无论 AI 的能力如何进步，通过学习 DSA 来提高个人的思维能力和基础编码能力的作用是始终不变的。

今天，我们从 Codeforces 2123C 开始。

问题： C. Prefix Min and Suffix Max

传送门：CF 2123C

问题描述

给定一个由互不相同的整数构成的数组 $a$。
每次操作中，您可以选择以下两种方式之一：

选取一个非空前缀 $^{\star}$，并将其替换为该前缀的最小值，或者
选取一个非空后缀 $^{†}$，并将其替换为该后缀的最大值。
注意，您可以选择整个数组 $a$。
对于每个元素 $a_i$ ，判断是否存在一系列操作可以将 $a$ 转换为 $[a_i]$ ，；即使数组 $a$ 仅包含一个元素，即 $a_i$ 。

输入输出格式

首先，在第一行接受一个整数 $T$ 作为测试样例的数量，对于每个测试样例：

接受一个整数 $n$ 作为数组 $a$ 的长度；
之后，在一行中接受 $n$ 个整数输入，作为数组 $a$ 的元素 $a_i$ 。具体的取值范围可在原网页中查看。

问题分析

对于数组 $a$ 中只有一个元素的情况，无需进行任何操作。

对于两个元素的情况，分别将整个数组作为前缀合后缀，其中的每个元素都可以经过一次操作将数组变成 $[a_i]$ 。

对于元素数量更多的情况，我们进行如下分析。
对于数组 $a$ 中的一个元素 $a_i$ ，它如果想让自己经过若干次上述操作，成为这个数组中唯一的 “胜者”，需要满足如下条件：

它是某个前缀的最小值；
它是某个后缀的最大值。

如果 $a_i$ 满足前者，则可将其所属前缀替换为 $a_i$ 。并将除它以外的后缀替换为其最大值，此时数组长度为 $2$，显然，此时每个元素都可以通过将整个数组作为前缀合后缀，取最小值合最大值来得到最终的数组 $[a_i]$ ，反之亦然。
如果元素 $a_i$ 不满足上述两个条件之一，可以证明，它不可能经过上述操作，成为数组中的唯一元素。

设 $a_p$ 是前缀 $[a_1, \cdots,a_i]$ 的最小值， $a_s$ 是后缀 $[a_i,\cdots,a_n]$ 的最大值，那么有 $p<i<s$ 且 $a_p<a_i<a_s$ 。
如果我们试图通过找到比 $a_p$ 更小的元素来移除 $a_p$ ，我们至少需要移除从 $a_1$ 到 $a_{i+1}$ 的元素，此时 $a_i$ 被移除了。
通过寻找比 $a_s$ 更大的元素来移除 $a_s$ 的做法同理。
反之，我们通过使用包含 $a_p$ 的后缀来移除 $a_p$ ，此时 $a_i$ 也在这段后缀中，因为 $a_i$ 不是这段后缀的最值，因此必定会被移除。
使用包含 $a_s$ 的前缀来移除 $a_s$ 的做法同理。

以上，我们证明了我们的思路的合理性，接下来就是将它转化为代码。

正确处理输入；
对于每个测试用例，记录下每段前缀的最小值合后缀的最大值；
对比原数组中元素与前缀/后缀数组中对应下标的元素，若相同，说明该元素是该前缀/后缀的最值，符合题意。

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void solve()
{
    int n;
    cin >> n;
    // 为了方便理解，从 1 开始使用下标
    vector<int> a(n + 1), pre(n + 1, INT_MAX), suf(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = min(pre[i - 1], a[i]);
    }

    for (int i = n; i >= 1; i--)
    {
        suf[i] = max(suf[i + 1], a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << (a[i] == pre[i] || a[i] == suf[i] ? 1 : 0);
    }
    cout << '\n';
}

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

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

总结

本题在算法上没有什么奇技淫巧，只是需要在读题之后思考合推理，分析问题描述中的条件，推测出关键结论。
本题的时空复杂度均为 $O(n)$ 。