ABC431C 机器人工厂
大约 3 分钟贪心
ABC431C 机器人工厂
【算法标签】 贪心
【语法标签】 :数组、sort、while循环、for循环、cin/cout
高桥君可以将 1 个头部零件 和 1 个身体零件 组合制作 个机器人。
如果头部零件的重量 大于 身体零件的重量,机器人就会倒下。
现在高桥君拥有 个头部零件和 个身体零件。
第 个 头部零件的重量为 克,第 个 身体零件的重量为 克。
高桥君希望通过合理组合零件,制作总共 个不会倒下的机器人。
请判断高桥君是否能达成目标。
注意:
- 个零件不能用于制作多个机器人
- 个机器人也不能使用 个以上的头部零件(或身体零件)
解题思路
这是一道典型的贪心匹配问题,核心思路是用双指针策略,尽可能多的匹配出 “头重量 ≤ 身体重量” 的组合。
核心步骤
排序:将头部零件数组
a和身体零件数组b分别按从小到大排序。目的是让 “小的头零件优先匹配小的身体零件”,这样能为后续更大的头零件留出匹配空间,最大化匹配数量。
双指针匹配:
- 初始化两个指针
i(遍历头部零件)、j(遍历身体零件),以及计数器cnt。 - 当
i ≤ n且j ≤ m时循环:- 如果当前头零件重量
a[i] ≤ b[j],说明可以匹配成功,cnt++,同时两个指针都向后移动(两个零件都被使用)。 - 如果
a[i] > b[j],说明这个身体零件无法匹配任何未使用的头零件(因为头数组已排序,后面的头只会更大),直接j++跳过这个身体零件。
- 如果当前头零件重量
- 初始化两个指针
判断结果:如果最终匹配数量
cnt ≥ K,说明可以制作出 K 个合格机器人,输出Yes;否则输出No。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int M = 2e5 + 5;
int a[N], b[M];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
}
// 对两个数组从小到大排序
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int cnt = 0;
int i = 1, j = 1;
while (i <= n && j <= m) {
if (a[i] <= b[j]) {
// 可以匹配成功,计数+1,两个指针同时后移
cnt++;
i++;
j++;
} else {
// 当前身体零件太小,无法匹配任何未使用的头零件,跳过
j++;
}
}
if (cnt >= k) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}算法复杂度分析
时间复杂度:
主要耗时在两次排序上,双指针遍历的时间复杂度为
,可忽略不计。
空间复杂度:
存储两个零件数组所需的额外空间。
总结
这道题的关键在于理解贪心策略的正确性:通过从小到大排序后用双指针匹配,能保证我们用最少的 “资源” 完成尽可能多的有效匹配。这种 “小配小” 的思路是解决此类匹配问题的经典技巧。
