自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

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

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

以下是正文

思路一

对于一个当前全部为 $1$ 的区间 $[l,r]$，考虑它与包含它的区间哪一个更优。考虑左端点左边一个位置 $l-1$，若 $l-1$ 为 $1$ 则左端点向左移显然更优；若 $l-1$ 为 $0$，注意到若将 $l-1$ 位置修改为 $1$ 并将左端点向左移只可能更优，不可能更劣——因为此时 $x$ 和 $y$ 同时增大 $1$，$x-y$ 不变，且这样有助于将更靠左的 $1$ 与现在的区间相连接。右端点同理。

因此，一种最优的区间即为 $[1,n]$，即：将所有为 $0$ 的数改为 $1$ 时，$x-y$ 取到最大值，为原序列中 $1$ 的个数。

思路二

一个显然的结论：被我们从 $0$ 修改为 $1$ 的位置一定会属于最终序列的唯一的最长连续 $1$ 子段，否则我们可以不进行对应位置的修改，使得 $x$ 不变，且 $y$ 减小。

因此，$x-y$ 可以转化为“在最终的最长连续 $1$ 子段中，在原序列中为 $1$ 的位置个数”。于是我们只需将所有的 $1$ 连成一个区间即可——设最左边一个 $1$ 的位置为 $l$，最右边一个 $1$ 的位置为 $r$，则使得 $x-y$ 最大的充要条件为 $[l,r]$ 区间里的 $0$ 全部被改为 $1$，因此将这一段改为 $1$ 即可。（同理也可以全部改为 $1$）

代码

思路一

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int cnt=0;//记录 1 的个数 
		for(int i=1;i<=n;++i)
		{
			int x;
			scanf("%d",&x);
			cnt+=x;
		}
		printf("%d\n",cnt);
		for(int i=1;i<=n;++i)
			printf("1%c",i<n?' ':'\n');
	}
	return 0;
}

思路二

#include<bits/stdc++.h>
using namespace std;
const int max_n=1e5+5;
int a[max_n];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int cnt=0;//记录 1 的个数 
		for(int i=1;i<=n;++i)
		{
			scanf("%d",a+i);
			cnt+=a[i];
		}
		printf("%d\n",cnt);
		int l=1,r=0;//若不存在 1，则不用修改
		for(int i=1;i<=n;++i)
		{
			if(a[i])
			{
				l=i;
				break;
			}
		}
		for(int i=n;i>=1;--i)
		{
			if(a[i])
			{
				r=i;
				break;
			}
		}
		for(int i=l;i<=r;++i)
			a[i]=1;
		for(int i=1;i<=n;++i)
			printf("%d%c",a[i],i<n?' ':'\n');
	}
	return 0;
}

PS：若题目要求 $x-y$ 尽量大的同时 $y$ 尽量小，则必须选用第二份代码。（此题没有要求）