题目 3316: 蓝桥杯2025年第十六届省赛真题-数组翻转

题目 3316: 蓝桥杯2025年第十六届省赛真题-数组翻转
时间限制: 3s 内存限制: 512MB 提交: 101 解决: 24
题目描述
小明生成了一个长度为 n 的正整数数组 a1, a2, . . . , an，他可以选择连续的一 段数 al , al+1, ..., ar，如果其中所有数都相等即 al = al+1 = ... = ar，那么他可以获 得 (r − l + 1) × al 的分数。 

在选择之前，为了让分数尽可能大，他决定先选择数组中的一段区间，对 其进行左右翻转。他想知道在对数组进行翻转之后他能获得的最大分数是多少？ 

提示：当翻转 al 到 ar 这段区间后，整个数组会变为 a1, a2, . . . , al−1, ar , ar−1, . . . , al+1, al , ar+1, . . . , an

输入格式
输入共两行。

第一行为一个正整数 n。

第二行为 n 个由空格分开的正整数 a1, a2, . . . , an。

输出格式
输出共 1 行，一个整数表示答案。

样例输入复制
7
4 4 3 3 2 1 3
样例输出复制
9
提示
【样例说明】 

翻转区间 [5, 7]，数组变为 4, 4, 3, 3, 3, 1, 2，最大分数为选择三个 3。 

【评测用例规模与约定】 

对于 20% 的评测用例，n ≤ 500。 

对于 100% 的评测用例，n ≤ 106，ai ≤ 106。

1.分析

        记录连续出现相同数字的个数的前两最大值。因为可以通过反转把这两个链接起来。

        最后统计计算最大值。

2.代码

        

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int MAX = 1e6+10;
typedef long long LL;
int n, a[MAX],re;
int b[MAX][2];
set<int> m;
int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}a[n] = -1;int t=a[0], s=0;m.insert(a[0]);for (int i = 1; i <= n; i++) {if (a[i] != t) {int num = i - s;if (num > b[t][0]) b[t][0] = num;else if (num > b[t][1]) b[t][1] = num;t = a[i];s = i;m.insert(t);}}for (auto it : m) {int sum = it * (b[it][0] + b[it][1]);re = max(re, sum);}cout << re << endl;return 0;
}