题目翻译

给定一个长度为

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：

CPP

#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）

题解：CF2106D Flower Boy

文章操作

题目翻译

思路

Code：

相关推荐

评论

题解：CF2106D Flower Boy