自动搬运

查看原文

来自洛谷，原作者为

	HYdroKomide I hate unfair games.

搬运于2025-08-24 22:35:04，当前版本为作者最后更新于2022-01-03 21:22:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

题目里说的挺简洁明白的，换句话说也可以是最小化相邻字符不同的个数。

很明显，这个也可以理解成：每次取所有串前面一样的数，使取的次数最少。

思路：

首先，取的方法决定，该取一个数就一定要把这一个串前面的这个数全部取出来，所以一个串取的次数最少就是相邻字符不同的个数再 $+1$。

每次要把所有的串前面的数都取出来，所以每个串取的次数都应该考虑。整体能够取的次数就是所有串能取次数的最大值。

然后就出来一份代码：

#include<iostream>
#include<cstring>
#define ri register int
using namespace std;
int n,l,tot,cnt,maxcnt;
string s;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(ri i=1;i<=n;i++){
		cin>>s;
		l=s.length(),cnt=0;
		tot+=l;//一共相邻的字符数，就是全部字符的个数-1
		for(ri j=1;j<l;j++)
			if(s[j]!=s[j-1])//求相邻字符不同的个数
				cnt++;
		maxcnt=cnt>maxcnt?cnt:maxcnt;//取最大值
	}
	tot--;
	cout<<tot-maxcnt<<endl;//最后减去不同的个数
	return 0;
}

然而只有 50pts。

原因应该很明显，一个串的开头可能是 $0$ 或者 $1$，但是要是取的话，第一次可能取的字符不能是这个串的开头。换句话说，第一次取的如果是 $0$，但是这个串的开头是 $1$，那么这个串暂时取不了，所以此时其实应该再多算一次。

所以我们对于每个串，都同时考虑最先取 $0$ 或 $1$ 的情况，然后取这两种情况的最优方案即可。

程序如下：

#include<iostream>
#include<cstring>
#define ri register int
using namespace std;
int n,l,tot,cnt0,cnt1,maxcnt0,maxcnt1,maxcnt;
string s;
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(ri i=1;i<=n;i++){
		cin>>s;
		l=s.length(),cnt0=cnt1=0;
		tot+=l;
		if(s[0]=='0')cnt1++;//如果字符串开头是0，那么一开始取1的次数+1
		if(s[0]=='1')cnt0++;//反之亦然
		for(ri j=1;j<l;j++)
			if(s[j]!=s[j-1])
				cnt0++,cnt1++;
		maxcnt0=cnt0>maxcnt0?cnt0:maxcnt0;
		maxcnt1=cnt1>maxcnt1?cnt1:maxcnt1;
	}
	maxcnt=min(maxcnt0,maxcnt1);//取其最小值
	tot--;
	cout<<tot-maxcnt<<endl;
	return 0;
}

THE END