自动搬运

查看原文

来自洛谷，原作者为

	xiaoliebao1115 real life

搬运于2025-08-24 22:57:00，当前版本为作者最后更新于2024-05-16 18:58:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

大体思路

计算出连续的 $0$ 和 $1$ 的个数，记为 $a$ 数组，根据这些数以两个为分界点求解，分最大值、最小值两种情况讨论。

求连续的 $0$ 和 $1$ 的个数是这样，下文 $a$ 数组大小记为 $cnt$。

for(int i=0;i<s.size();i++)
{
	if(s[i]!=s[i-1]) 
	{
		cnt++;
		a[cnt]=1;
	}
	else a[cnt]++;
}

最大值

找到与 $a$ 数组端点最接近的大于等于 $2$ 的数，从该数出发一直操作即可。

int ansmax=0;
for(int i=1;i<=cnt;i++)
{
	if(a[i]>=2)
	 ansmax=max(ansmax,max(i,cnt-i+1));
}

最小值

最小值的理论下界是除了第一次操作和最后一次操作外，保证一次操作删掉两个数，也就是 $cnt\div 2+1$ 。

分两类讨论：能达到理论下界或不能。

当 $a$ 数组中有一段连续的 $1$ 长度过大时就不能，可以分在边缘和不在边缘两种情况讨论，具体可见代码。

if(i==sum||i==cnt)//边缘
{
	if(sum>cnt-sum-1) ansmin=sum+1;
  //如何判断长度过大以及答案
	continue;
}
//非边缘
if(sum>cnt-sum-2) ansmin=sum+2;
//如何判断长度过大以及答案

剩下的长度小一点的一定可以达到理论下界，因为找到最靠近中间点的两个大于等于 $2$ 的数，一定可以对这两个数进行操作使得这两个数到边缘剩下的距离相等。

//sum 是连续 1 的长度
int sum=0,ansmin=INT_MAX;
for(int i=1;i<=cnt;i++)
{
	if(a[i]==1) sum++;
	else sum=0;
	//此处省略判断长度过大的代码
}
if(ansmin==INT_MAX) ansmin=cnt/2+1;

最后要特判 $a$ 数组都为 $1$ 的情况，这种情况无法操作，其他情况都可以将数组删至只剩一个数。