AcWing 3817. 数组

原题链接

题目描述

给定一个长度为 $n_A$ 的非降序整数数组 $A$ 和一个长度为 $n_B$ 的非降序整数数组 $B$ 。

请问，能否从 $A$ 中挑选 $k$ 个数，从 $B$ 中挑选 $m$ 个数，使得在 $A$ 中挑选出的任何数都严格小于在 $B$ 中挑选出的任何数。

输入格式

第一行包含两个整数 $n_A,n_B$ 。

第二行包含两个整数 $k,m$ 。

第三行包含 $n_A$ 个整数 $a_1,a_2,…,a_{nA}$ 。

第四行包含 $n_B$ 个整数 $b_1,b_2,…,b_{nB}$ 。

输出格式

共一行，能则输出 YES，否则输出 NO。

数据范围

$1≤nA,nB≤10^5$ ,
$1≤k≤n_A$ ,
$1≤m≤n_B$ ,
$-10^9≤a_i,b_i≤10^9$ 。
保证 $A$ 和 $B$ 都是非降序数组。

样例

输入样例1：

输出样例1：

YES

输入样例2：

输出样例2：

NO

输入样例3：

输出样例3：

YES

思路

非降序数组，可能是升序数组（我交的时候是升序数组，WA了排个序就行）。

这里 $A$ 和 $B$ 都是升序数组，题意是要从 $A$ 中选 $k$ 个数，都严格小于 $B$ 中选 $m$ 的个数。贪心的思想，选 $A$ 数组中最小的 $k$ 个数，选 $B$ 数组中最大的 $m$ 个数即可。

这里只要比较 $A_{k - 1}$ 和 $B_{n - m}$ 的大小即可。按照前面的思想， $A_{k - 1}$ 是 $A$ 中选出来的最大值， $B_{n-m}$ 是 $B$ 中选出来的最小值。

代码

C++

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int A[N], B[N];

int main()
{
    int a, b, k, m;
    scanf("%d %d %d %d", &a, &b, &k, &m);
    for ( int i = 0; i < a; i ++ ) scanf("%d", &A[i]);
    for ( int i = 0; i < b; i ++ ) scanf("%d", &B[i]);
    printf("%s\n", A[k - 1] < B[b - m] ? "YES" : "NO");
    return 0;
}

Java

import java.util.*;

public class Main
{
    private static Scanner in = new Scanner(System.in);
    private static final int N = (int) (1e5) + 5;
    private static int A[] = new int[N], B[] = new int[N];
    
    public static void main(String args[])
    {
        int a = in.nextInt(), b = in.nextInt(), k = in.nextInt(), m = in.nextInt();
        for ( int i = 0; i < a; i ++ ) A[i] = in.nextInt();
        for ( int i = 0; i < b; i ++ ) B[i] = in.nextInt();
        System.out.printf("%s\n", A[k - 1] < B[b - m] ? "YES" : "NO");
    }
}