题解：P12159 [蓝桥杯 2025 省 Java B] 数组翻转

蒟蒻的我第一次在洛谷写题解(上一次的寄了)，还请多包涵不足的地方。

问题描述。 给定长度为

n

的正整数数组

a_1,a_2,\dots,a_n

。小明可以先对数组中任意一段区间

[l,r]

做一次翻转（左右颠倒），然后从翻转后的数组中选取一段所有元素相等的子数组获得得分，若选取的区间长度为

L

，元素值为

v

，则得分为

L\times v

。问小明能获得的最大得分。

样例说明。
样例输入：

CPP

7  
4 4 3 3 2 1 3

翻转区间

[5,7]

后数组变为

4,4,3,3,3,1,2

，此时选取那 3 个连续的 3，可得分数

3\times 3=9

，为最优。

关键观察。
翻转操作的唯一作用，是可以将原数组中相同值

v

的两段不相邻的连续区间调换位置，使它们在翻转后相邻，从而合并为一段更长的相同值区间。
若不翻转，则对于值

v

，只能获取它在原数组中某一段最大连续长度

L_{\max}

，得分为

L_{\max}\times v

。
若允许一次翻转，则对于每个值

v

，可以选择原数组中两段连续且值都为

v

的区间，其长度分别为

L_1,L_2

，通过翻转把它们拼接到一起，获得长度

L_1+L_2

的区间，得分为

(L_1+L_2)\times v

。最优情况下，对于每个

v

，应选其最长的两段连续区间。

算法实现。

使用一次从左到右的扫描。
令 per[i] 表示以位置 $i$ 为结尾的、且值相同的最长连续段的长度。
当 $a_i=a_{i-1}$ 时，per[i]=per[i-1]+1；否则，表示一段结束，将该段长度 per[i-1] 记入哈希表 mp[a_{i-1}]，更新此值的「第一长」和「第二长」；然后重置 per[i]=1。
扫描结束后，哈希表 mp[v] 中存有值为 $v$ 的所有连续段的「第一长」 $f_1$ 和「第二长」 $f_2$ 。对每个键值对 $(v,(f_1,f_2))$ ，计算得分 $v\times(f_1+f_2)$ ，取最大。
时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ （用于存储 per 数组与哈希表）。

代码如下。

CPP

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll N = 1e6 + 5;

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n+5), per(n+5);
    map<int, pair<ll, ll>> mp;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n + 1; i++) {
        if (a[i] == a[i - 1]) {
            per[i] = per[i - 1] + 1;
        } else {
            per[i] = 1;
            auto &[firs, seco] = mp[a[i - 1]];
            if (per[i - 1] > firs) {
                seco = firs;
                firs = per[i - 1];
            } else {
                seco = max(seco, per[i - 1]);
            }
        }
    }

    ll ans = 0;
    for (auto [x, pa] : mp) {
        auto [firs, seco] = pa;
        ans = max(ans, x * (firs + seco));
    }

    cout << ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析。

扫描一遍数组维护 per 数组与更新哈希表，时间 $O(n)$ ；
最后遍历哈希表键值对，时间 $O(m)$ ，其中 $m$ 为不同值的数量，显然 $m \leq n$ ，故总时间 $O(n)$ 。
空间上，per 占 $O(n)$ ，哈希表最坏也为 $O(n)$ 。

这样就能在

n \le 10^6

时依然保持线性通过。

题解：P12159 [蓝桥杯 2025 省 Java B] 数组翻转

文章操作

相关推荐

评论

题解：P12159 [蓝桥杯 2025 省 Java B] 数组翻转