「EZEC-5」修改数组
题目描述
给定一个长度为 $n$、元素由 $0$ 或 $1$ 组成的数组。
现在可以**选择若干(可以为 0)个值为 $0$ 的元素,将其修改为 $1$**。
记:
- $x$ 为数组中最长连续 $1$ 子段的长度(规定,若所有数均为 $0$,则 $x$ 为 $0$);
- $y$ 为修改的元素的个数。
求要怎么修改才能使 $x-y$ **最大**,并构造一个方案(输出修改后的数组)。
输入输出格式
输入格式
**本题含有多组数据。**
第一行一个整数 $T$ 表示数据组数。
接下来 $2\times T$ 行,每 $2$ 行表示一组数据。
在一组数据中,第一行一个整数 $n$,表示数组的长度;
第二行 $n$ 个整数(0 或 1),表示给定的数组。
输出格式
共 $2\times T$ 行,每 $2$ 行表示一组数据。
在一组数据中,第一行输出一个整数表示 $x-y$ 的最大值;
第二行 $n$ 个整数(0 或 1)表示修改以后的数组。**如有多个方案,任意输出一种即可。**
输入输出样例
输入样例 #1
1
1
1
输出样例 #1
1
1
输入样例 #2
2
3
1 0 1
5
0 1 0 1 0
输出样例 #2
2
1 1 1
2
0 1 1 1 1
说明
**本题采用捆绑测试。**
对于所有数据,保证 $T\le10,1\le n\le 10^5$,数组元素 $\in \{0,1\}$。
- Subtask 1(70 points):保证 $1\le n\le 10$;
- Subtask 2(30 points):无特殊限制。