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

溶金落梧桐 · 2026-11-09 17:27:07 · 题解

有一个较为明显的思路，我们一定会留在一开始就连续且相同的数字，而剩下的数字我们都会进行题目中的操作。

先假设一件事情，如果我们找出了要留的数字区间，那答案是多少？

只有两个情况：

1. 左边的数字全部移动到右边，该操作会让左边的数字操作两次，右边的数字操作一次
2. 右边的数字全部移动到左边，该操作会让右边的数字操作两次，左边的数字操作一次

答案肯定是上述两个情况的较小值。

那应该怎么找出要留的数字区间呢？其实不需要找出，我们把所有的连续相同的数字区间都枚举一遍，找出最佳答案就行。

注意边界数据，时间复杂度 O(n)。

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=1,r=1,pre=-1,ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        if(a[i]==pre){
            r=i;
        }else{
            l=r=i;    
        }
        ans=min({ans,(l-1)*2+n-r,(n-r)*2+(l-1)});
        pre=a[i];
    }
    cout<<ans;
}