题解：B4583 [合肥市小学组 2026 T3] 魔法水晶

· · 题解

题目传送门

思路

因为每次可以左右操作，那么最优策略显然是把中间连续相同的那一段保留，不然不管你怎么删左右两端的总是没有中间相同那一段长。

设中间保留的段为 [l,r]，全部等于一个相同的数，那么：

那么最后的最小操作数也就是 L + R + \min(L,R)。

::::info[为什么不是 L+R？]{open} 凭直觉，左边有 L 个，右边有 R 个，想要全部删掉肯定要 L + R 次，但真的是这个吗？你忽略了一点——操作后会在与操作相反的那一端增加水晶！因此，需要看左右两端哪一端多余水晶更少，然后把他们删去，这样不管怎么样都能把最长连续相同段保留了，操作数也就是原先的加上 \min(L,R)，也就是 L + R + \min(L,R)。 ::::

好了，然后用双指针 i,j 扫一遍相同段就行了，注意，需要在每个 i 循环末尾让 i \gets j，不然会重复查找，让复杂度飙升至 \mathcal{O}(n^2)。

代码

::::success[AC Code]{open}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int ans = 1e9; // 初始化一个极大数，来求最小值
    for (int i = 1; i <= n; ++i) {
        int j = i;
        while (j + 1 <= n && a[j + 1] == a[i]) ++j; // 双指针，也可以用 for 循环写
        int L = i - 1; // 把对应的 L,R 算出来
        int R = n - j;
        ans = min(ans, L + R + min(L, R)); // 计算答案
        i = j; // 不重复查找
    }
    cout << ans;
    return 0;
} // 完结撒花

:::: 时间复杂度大致为 \mathcal{O}(n)，可以通过 n = 10^5 的数据。