P7285 「EZEC-5」修改数组

传送门

题目简述

给定一个长度为 $n$、元素由 $0$ 或 $1$ 组成的数组。

现在可以选择若干（可以为 $0$）个值为 $0$ 的元素，将其修改为 $1$。

记：

1. $x$ 为数组中最长连续 $1$ 子段的长度（规定，若所有数均为 $0$，则 $x$ 为 $0$；

2. $y$ 为修改的元素的个数。

求要怎么修改才能使 $x-y$ 最大，并构造一个方案（输出修改后的数组）。

初步分析

我们要 $1$ 尽量长，修改的尽量少。

发现

我们在把题读一遍

$x$ 为数组中最长连续 $1$ 子段的长度

那么每修改一个数，$x$ 会加 $1$

$y$ 为修改的元素的个数

那么每修改一个数，$y$ 会加 $1$

解决

于是题目变成了给的数组中有多少个 $1$

而要输出改后的数组，就可以全部输出 $1$ 即可

因为不管修改了多少个，给的数组的 $1$ 的个数不会变

题目：如有多个方案，任意输出一种即可。

代码

#include<iostream>
using namespace std;
int main(){
  int t;//t组数据
  cin>>t;
  while(t--){
    int n,sum=0;//n为数组长度,sum记录1的个数
    cin>>n;
    for(int i=0;i<n;i++){
      int x;
      cin>>x;
      if(x==1)sum++;
    }
    cout<<sum<<endl;
    for(int i=0;i<n;i++)cout<<1<<" ";//可以全部输出 1。
    cout<<endl;//记得每个数据结束换行
  }
  return 0;
}