【题解】洛谷 P7285 「EZEC-5」修改数组

wsyhb · 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 尽量小，则必须选用第二份代码。（此题没有要求）