每日一题-贪心数组_!!k ? k!!!! !!! ,, nnm! j是心 vvv bbnb v v b v b n

数组

来自acwing每日一题

给定一个长度为 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

很简单的一道贪心题目。

题目意思就是从a数组里面任意取k个数，在b数组里面任意取m个数，如果这k个数都小于m个数中的任何一个就输出yes，上述例子，a数组取完了，b数组只取三个，(那我们取后面三个5)，可见这个a里面取的五个数字都小于5，所以输出YES。

思路就是，比较a[k] 和 b[nb-m+1]的大小就行了，

#include <iostream>
using namespace std;
const int N = 1e5+5;
int a[N], b[N], na, nb, k, m;
int main()
{
    cin >> na >> nb;
    cin >> k >> m;
    for ( int i = 1; i <= na; ++i ) cin >> a[i];
    for ( int i = 1; i <= nb; ++i ) cin >> b[i];
    
    
    if ( a[k] < b[nb-m+1] ) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16