专栏文章

题解：AT_abc431_c [ABC431C] Robot Factory

ddrac1
AT_abc431_c题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min9imzv
此快照首次捕获于
2025/12/01 22:46
3 个月前
此快照最后确认于
2025/12/01 22:46
3 个月前
查看原文

题目大意

有 NN 个头部零件和 MM 个身体零件，每个头部零件需要与一个身体零件配对。配对的条件是：对于第 ii (1≤i≤N1 \le i \le N) 个头部零件（重量为 aia_i）和第 jj (1≤j≤M1 \le j \le M) 个身体零件（重量为 bjb_j），需要满足 ai≤bja_i \le b_j。
如果能够形成至少 KK 个满足条件的配对，则输出 Yes，否则输出 No。

解题思路

  • 将 AA 序列排序和 BB 序列排序后，可以用两个指针标记它。
  • 一个标记 AA 序列（ll 指针），一个标记 BB 序列（rr 指针）。
  • ll 指针和 rr 指针都从 00 开始标记，做双指针。
  • 当满足要求，指针 ll 和 rr 往右跳一格。
  • 不然，就是身体部件重量不够，rr 往右跳一格。

优化思路

  • 不妨看到，无论够不够格，rr 都会往右跳一格。
  • 所以，只需要把指针 rr 变成一个循环就可以了。

代码实现

方法一：标准双指针

CPP
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
void solve();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) solve();
	return 0;
}
void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n), b(m);
	for (auto &t : a) cin >> t; //遍历 a 数组以便输入
	for (auto &t : b) cin >> t; //遍历 b 数组以便输入
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int l = 0, r = 0, cnt = 0;
	while (l < n && r < m) {
		if (a[l] <= b[r]) {
			cnt++;
			l++;
			r++;
		} else r++;
	}
	if (cnt >= k) cout << "Yes\n";
	else cout << "No\n";
	return ;
}

方法二：优化版本

此代码是 Nathan 老师的代码再次优化而来。
CPP
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
void solve();
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) solve();
	return 0;
}
void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n), b(m);
	for (auto &t : a) cin >> t; //遍历 a 数组以便输入
	for (auto &t : b) cin << t; //遍历 b 数组以便输入
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	int l = 0, cnt = 0;
	for (int i = 0; i < m; i++) {
		if (a[l] <= b[i]) {
			l++;
			cnt++;
		}
	}
	if (cnt >= k) cout << "Yes\n";
	else cout << "No\n";
	return ;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...