自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:50:27，当前版本为作者最后更新于2023-09-27 21:37:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

贪心。

约定：

对于一组连续两个颜色都相同的格子，在下文中将被称作双连。

对于一组连续两个的格子，在下文中将被称作连双。

对于一组连续三个颜色都相同的格子，在下文中将被称作三连。

对于一组连续三个的格子，在下文中将被称作连三。

思路：

观察 $k$ 的取值，我们会发现 $k$ 至少为 $3$。这就说明，我们完全可以保证改动后的格子与两边不同色。那么，$k$ 的存在就没有多少意义了，只需要标记出哪些格子需要变色即可。

初始时先统计出未修改时的答案，再进行贪心的修改，让答案最大化。

显然的，对于一个三连，我们可以通过改变中间格子，而使答案块数加上 $2$。而对于双连，我们改变其中任意一个格子，收益都只为 $1$。

所以我们先枚举每一个连三，判断是否是三连，是则变中间格，不是略过，然后再枚举连双进行判断并依据判断结果进行改变即可。

这样显然能够最大化 $m$ 次修改所带来的收益。

代码：

#include<bits/stdc++.h>
using namespace std;
int jsq=-1;//修改赋特殊值保证不同不可能被判定成双/三连
int main(){
    int t;cin>>t;
    while(t--){
        int n,m,k;cin>>n>>m>>k;
        int c[500005]={},ans=0;
        for(int i=1,flag=(--jsq);i<=n;i++){
            cin>>c[i];
            if(flag!=c[i]) ans++,flag=c[i];//初始统计答案
        }
        for(int i=2;m&&i<n;i++) if(c[i-1]==c[i]&&c[i]==c[i+1]) m--,c[i]=(--jsq),ans+=2;//枚举连三判断三连
        for(int i=1;m&&i<n;i++) if(c[i]==c[i+1]) m--,c[i]=(--jsq),ans++;//枚举连双判断双连
        cout<<ans<<endl;
    }
    return 0;
}