题目描述
给定一个长度为 nA 的非降序整数数组 A 和一个长度为 nB 的非降序整数数组 B。
请问,能否从 A 中挑选 k 个数,从 B 中挑选 m 个数,使得在 A 中挑选出的任何数都严格小于在 B 中挑选出的任何数。
输入格式
第一行包含两个整数 nA,nB。
第二行包含两个整数 k,m。
第三行包含 nA 个整数 a1,a2,…,anA。
第四行包含 nB 个整数 b1,b2,…,bnB。
输出格式
共一行,能则输出 YES,否则输出 NO。
数据范围
1≤nA,nB≤105,
1≤k≤nA,
1≤m≤nB,
−109≤ai,bi≤109。
保证 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
算法1
(计算) $O(1)$
1.直接比较a[k-1]和b[-m]
时间复杂度
参考文献
python3 代码
na, nb = map(int, input().split())
k, m = map(int, input().split())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
x = a[k-1]
y = b[-(m)]
if x < y:
print('YES')
else:
print('NO')
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int na, nb;
cin >> na >> nb;
int k, m;
cin >> k >> m;
int a[na];
for (int i = 0; i < na; i ++)
cin >> a[i];
int b[nb];
for (int i = 0; i < nb; i ++)
cin >> b[i];
int x = a[k - 1];
int y = b[nb - m];
if (x < y)
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
java 代码
import java.util.* ;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int na = scan.nextInt();
int nb = scan.nextInt();
int k = scan.nextInt();
int m = scan.nextInt();
int [] a = new int [na];
for (int i = 0; i < na; i ++)
a[i] = scan.nextInt();
int [] b = new int [nb];
for (int i = 0; i < nb; i ++)
b[i] = scan.nextInt();
int x = a[k - 1];
int y = b[nb - m];
if (x < y)
System.out.println("YES");
else
System.out.println("NO");
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla