题解：CF2106D Flower Boy

· · 题解

题目翻译

题目传送门（vjudge）

给定一个长度为 n 的数组 a 和一个长度为 m 的数组 b。

要在 a 中从左到右选取 m 个数按从左到右的顺序组成一个新的数列，使得选出来的数大于等于 b 数组中对应位置上的数。有可能不够选，因此可以将一个任意大小的数 k 插入到 a 数组中的任意位置（包括最前面和最后面），插入操作只能执行一次。

求 k 是多少。如果可以不用插入，则输出 0。如果插入了也无法选出 m 个数，则输出 -1。

思路

因为是要从左到右选取数字，所以我们可以贪心地选取数字，即从左往右遍历，只要当前数字大于等于 b 数组上对应位置的数字，就选取，维护一个数组 pre 来存储在每个位置能最多选取多少数字。然后枚举每一个空隙，看能否插入数字，插入的是什么数字，从而得到答案。

但是仅仅有从左到右得到的 pre 是不足以得到每个空隙的情况的，因此我们考虑从右到左进行一次贪心的选取，维护一个数组 erp 来存储每个位置上最多能选取多少个数。这样我们就得到了每个空隙的前缀和后缀，可以方便地得到每个空隙的情况。

因此，只要满足：

pre_i+erp_{i+1}=m-1

就说明 i 和 i+1 这个空隙里差一个数。而 k 的值为 b_{pre_i+1}。遍历找到最小值就是答案。

Code：

#include<bits/stdc++.h>
#define Iseri namespace
#define Nina std
#define Kawaragi int
#define Momoka main
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define ll long long
#define ull unsigned long long
#define endl "\n"
const int maxn=200005;

using Iseri Nina;

inline ll read(){//快读
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

//===========================================================

ll t,n,m,pre[maxn],erp[maxn],a[maxn],b[maxn],cnt;

Kawaragi Momoka(){
    t=read();
    while(t--){
        n=read(),m=read();
        for(ll i=1;i<=n;i++)a[i]=read();
        for(ll i=1;i<=m;i++)b[i]=read();

        //多测不清空，爆零两行泪TAT
        memset(pre,0,sizeof(pre));
        memset(erp,0,sizeof(erp));

        cnt=0;
        for(ll i=1;i<=n;i++){//求“前缀”
            if(a[i]>=b[cnt+1]&&cnt<m)cnt++;
            pre[i]=cnt;
        }
        cnt=0;
        for(ll i=n;i>=1;i--){//求“后缀”
            if(a[i]>=b[m-cnt]&&cnt<m)cnt++;
            erp[i]=cnt;
        }

        if(pre[n]>=m)printf("0\n");//如果最后一位能够最多选到m个数，那就不用插入啦！直接输出0
        else{
            ll ans=1145141919;//设极大值
            for(ll i=0;i<=n;i++){
                if(pre[i]+erp[i+1]==m-1)ans=min(ans,b[pre[i]+1]);
            }

            if(ans==1145141919)printf("-1\n");//如果遍历一遍都找不到，那就没办法了TAT，输出-1
            else printf("%lld\n",ans);
        }
    }
    return 0;
}

灵感来源：vjudge

提交记录：这里（vjudge）