CF1692E题解

__vector__ · 2022-06-16 14:48:01 · 题解

题目翻译

给你一个 n 个元素且只包含 1 或 0 两种元素的序列 a，以及一个正整数 s。
在一次操作中，你可以删掉第一个元素或最后的元素。
求使得剩下元素总和等于 s 的最小操作次数。

思路

考虑到只能在首尾删元素，可以将问题转化为：
在数列 a 中选择一个区间 [l,r]，使得 \sum_l^r a_i = s，并且这个区间必须是满足条件的区间中最长的。

暴力思路

显然可以暴力枚举每一个区间，前缀和 O(1) 判断当前区间总和是否为 s，然后更新答案。
复杂度 O(n^2)。

优化

首先设数列第 i 个元素的前缀和是 qzh_i。
枚举左端点的部分不太好优化，那就优化选择右端点的部分。
显然，固定了左端点 l 后，右端点 r 的前缀和值 qzh_r 也就固定了。可以将其算出来，等于 qzh_{l-1} + s。
而前缀和数组是升序的！
也就是说可以用 lower_bound，O(\log n) 把右端点求出来。
但是要注意，lower_bound 求出来的右端点 r，是第一个满足要求的 r，而因为要求区间最长，我们需要的是最后一个满足要求的 r，所以还要做一些处理。
算出 a_r 后面有多少个元素 0，设有 sum 个，将 r 跳到 r+sum - 1，也就是这些 0 元素的最后一个。
这道题就做完了。
复杂度 O(n \log n)。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=2e5+5;
    int t,n,s;
    int a[maxn];
    int qzh[maxn];//前缀和
    int len[maxn];
    //len[i] 代表第 i 个元素开始有多少个相邻的相同元素
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&n,&s);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                qzh[i]=qzh[i-1]+a[i];
            }
            for(int i=n;i>=1;i--)
            {
                if(i==n)
                {
                    len[i]=1;
                    continue;
                }
                if(a[i]==a[i+1])len[i]=len[i+1]+1;
                else len[i]=1;
            }
            if(qzh[n]<s)
            {
                printf("-1\n");
                continue;
            }
            int maxlen=0;
            for(int l=1;l<=n;l++)
            {
                int r=lower_bound(qzh+l,qzh+n+1,s+qzh[l-1])-qzh;
                if(a[r+1]==0&&r<n)r=r+1+len[r+1]-1;
                if(r==n+1)
                {
                    continue;
                }
                maxlen=max(maxlen,r-l+1);
            }
            printf("%d\n",n-maxlen);
        }
    }
}
int main()
{
    Main::main();
    return 0;
}