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

· · 题解

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

题意简述

有一排 n 颗魔法水晶，每次可以选择一种操作：

  1. 销毁最左边水晶，在最右边召唤一颗能量任意的水晶；
  2. 销毁最右边水晶，在最左边召唤一颗能量任意的水晶。

求最少操作次数，使所有水晶的能量相同。

思路分析

我们把原数组按连续相同的值分块。对于某一个块 [i,j-1]：

想要把左右两侧全部改成和块内相同，最优代价为：

\text{cost}=l+r+\min(l,r)

遍历所有连续块，取所有代价的最小值的和，就是答案。

复杂度

时间复杂度：O(n)，使用双指针遍历，每个元素只会访问一次。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,a[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int minn=INT_MAX;
    int i=1;
    while(i<=n){
        int j=i;
        while(j<=n&&a[j]==a[i]) j++;
        int l=i-1,r=n-j+1;
        minn=min(minn,(l+r+min(l,r)));
        i=j;
    }
    cout<<minn;
    return 0;
}