AcWing 3817：数组 ← 贪心算法

【题目来源】
https://www.acwing.com/problem/content/3820/

【题目描述】
给定一个长度为 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≤10^5,
1≤k≤nA,
1≤m≤nB,
−10^9≤ai,bi≤10^9。
保证 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

【算法分析】
☆★ 贪心是通过局部最优解，找到全局最优解。所以，贪心算法一般适用于单峰问题。
☆★ C++ 中 reverse() 函数的示例代码。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int a[maxn];

int main() {
    int n;
    cin>>n;
    
    for(int i=0; i<n; i++) cin>>a[i];
    reverse(a,a+n);
    for(int i=0; i<n; i++) cout<<a[i]<<" ";

    return 0;
}


/*
in:
5
1 3 5 7 9

out:
9 7 5 3 1
*/

【算法代码】

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
int a[maxn];
int b[maxn];

int main() {
    int na,nb,k,m;
    cin>>na>>nb>>k>>m;
    for(int i=0; i<na; i++) cin>>a[i];
    for(int i=0; i<nb; i++) cin>>b[i];

    reverse(b,b+nb);

    if(a[k-1]<b[m-1]) cout<<"YES";
    else cout<<"NO";

    return 0;
}


/*
in:
3 3
2 1
1 2 3
3 4 5

out:
YES
*/

【参考文献】
https://www.acwing.com/solution/content/120077/

 

原文地址：https://blog.csdn.net/hnjzsyjyj/article/details/142926899

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！