[数据结构与算法]【每日一题】【枚举】【思维】奕星的棋盘

• 博客主页: https://blog.csdn.net/qq_50285142
• 欢迎点赞👍收藏?关注?留言 📝 如有错误，敬请指正
• 🎈虽然生活很难，但我们也要一直走下去🎈

题目链接

题意：
有一个$2?n$的棋盘，上面有黑白棋子，可以把白棋子替换为黑棋子，要求使最后的黑棋子连通，求最小替换数

思路：
可以发现只有两行，一列的情况是有限的，而且只有四种，非常少，所以我们可以对不同情况进行分类讨论
为了方便，我们把每一列的情况做一个标号
第一行：0 0 1 1
第二行：0 1 0 1
对应标号 0 1 2 3
然后就是分情况讨论了：我们讨论两列有1的且相邻的情况，pre记录前一列有1的位置

第一种：
相邻的两列的其中一列有两个1
1 0 1
1 0 0
类似这样的情况
结果就是当前的位置减去前一个有1的位置再减一，只需要把红色的那个变为1就可以了

第二种：
0 0 1
1 0 0
两列的的1的位置不同，那么需要多替换一个，最优的情况是优先替换右边有1的那一列，替换之后，该列的标号就变为3了（注意进行改变）

第三种:
剩下的就是，列标号相同的，直接把两列1之间的0替换为1就可
1 0 0 1
0 0 0 0
类似这样的，把1之间的0替换一下就可以了，结果为$当前1的位置?前一列有1的位置?1$

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+5;

int a[N],n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		if(x)
		{
			if(a[i]) a[i] = 3;
			else a[i] = 2;
		}
	}
	
	int pre = -1,res = 0;
	
	for(int i=1;i<=n;i++)
	{
		if(a[i])
		{
			if(pre!=-1)
			{
				if(a[pre]==3 || a[i]==3) res += i - pre - 1;
				else if(a[pre]!=a[i]) res += i - pre,a[i] = 3;
				else res += i - pre - 1;
			}
			pre = i;
		}
	}
	cout<<res<<'\n';
	return 0;
}

往期优质文章推荐

• 💛💚C++ STL详解，超全总结(快速入门STL)
• 💛🧡【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）
• 💛💚区间贡献问题习题详解

如果我的文章对你有帮助，欢迎点赞＋评论+关注

欢迎微信搜索『行码棋』同名公众号，点击『获取资源』领取大量资源哦。