题目描述
给定一个长度为 $n_A$ 的非降序整数数组 $A$ 和一个长度为 $n_B$ 的非降序整数数组 $B$。
请问,能否从 $A$ 中挑选 $k$ 个数,从 $B$ 中挑选 $m$ 个数,使得在 $A$ 中挑选出的任何数都严格小于在 $B$ 中挑选出的任何数。
样例
输入样例1
3 3
2 1
1 2 3
3 4 5
输出样例1
YES
输入样例2
3 3
3 3
1 2 3
3 4 5
输出样例2
NO
输入样例3
5 2
3 1
1 1 1 1 1
2 2
输出样例3
YES
算法
$O(n)$
由于题目说明了$a[n]$和$b[n]$两个数组是非降序的,我们就默认这两个数组都是升序的。(其实我觉得严谨讲不一定,所以我第一遍做的时候还排了个序)。
题目要求从$a[n]$选$k$个数,因此我们要让选的数尽可能小,因此应该选择前$k$个数,这些数中最大的是$a[k-1]$。
题目要求从$b[n]$选$m$个数,因此我们要让选的数尽可能大,因此应该选择后$m$个数,这些数中最小的是$b[n2-m]$。
我们只需要判断$a[k-1]$和$b[n2-m]$的大小关系即可。
如果前者严格小于后者,说明是满足题意的,输出$YES$;
否则,输出$NO$。
时间复杂度
因为我们只用比较$a[k]$和$b[n2-m]$,这个步骤是$O(1)$的,读入数组的操作时$O(n)$的,因此总的时间复杂度是$O(n)$的
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n1,n2,k,m;
int a[N],b[N];
int main()
{
scanf("%d%d",&n1,&n2);
scanf("%d%d",&k,&m);
for(int i = 0;i<n1;i++)scanf("%d",&a[i]);
for(int i = 0;i<n2;i++)scanf("%d",&b[i]);
if(a[k-1]>=b[n2-m])puts("NO");
else puts("YES");
return 0;
}