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

beicige · 2025-07-18 10:06:08 · 题解

题意

给出一个长度为 n 的正整数数组 a_1, a_2, \dots , a_n 。可以对任意一个区间进行翻转。然后找出连续相同数字区间长度与相同数字之积的最大值。

思路

很明显题目要求把两段所有数都相同的区间合并。所以我们可以求出每一个数字连续出现次数的最大值和次大值。对于每一个数字，这样两个区间通过翻转合并后的长度一定为最长。

然后枚举所有数字可获得的分数，求出得分最大值即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000010],m[1000010][3],cnt,ans,ma=-1,mi=INT_MAX;
//m数组存储每一个数字的最大和次大长度，ma和mi存储数字的最大值和最小值 
//cnt存储当前长度 
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin>>n; 
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ma=max(ma,a[i]),mi=min(mi,a[i]);//记录最大值和最小值 
    }
    for(int i=1;i<=n;i++){
        cnt++;//当前长度增加 
        if(a[i]!=a[i+1]||i==n){//如果下一位数字与当前数字不相同 
            if(cnt>m[a[i]][1]) m[a[i]][2]=m[a[i]][1],m[a[i]][1]=cnt;//是目前最长，则把原本最长下调至第二长 
            else if(cnt>m[a[i]][2]) m[a[i]][2]=cnt; //修改为第二长 
            cnt=0;//注意计数器清零 
        }
    }
    for(int i=mi;i<=ma;i++){//从所有数字的最小值到最大值 
        ans=max(ans,(m[i][1]+m[i][2])*i);//ans存储答案。最长与次长之和是翻转后的长度，与当前数字相乘得到分数 
    }
    cout<<ans;
}