题解：AT_joi2009yo_c 連鎖

zby0501_ · 2025-03-02 14:30:46 · 题解

思路：

这题看起来很难，但其实模拟一下就可以了。

我们根据题意，每次选择一个珠子，并改变它的颜色然后进行消除。最后把消完后的结果取一个最小值就可以了。

消的时候不用真的消，只要双指针模拟一下就行啦。

最后，请注意换行！！

代码：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,a[10005];
int f(int l){
    int r=l+1,s=n;
    while(1){
        int c=a[l],sum=0;
        while(a[l]==c && 1<=l) --l,++sum;
        while(a[r]==c && r<=n) ++r,++sum;
        if(sum<4) return s;
        s-=sum;
    }
}
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int ans=2e9;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i){
        for(int j=1;j<=3;++j){
            swap(a[i],j);
            ans=min(ans,f(i));
            swap(a[i],j);
        }
    }
    cout<<ans<<'\n';
    return 0;
}