题解：AT_abc431_c [ABC431C] Robot Factory

drac1 · 2025-11-12 18:18:21 · 题解

题目大意

有 N 个头部零件和 M 个身体零件，每个头部零件需要与一个身体零件配对。配对的条件是：对于第 i (1 \le i \le N) 个头部零件（重量为 a_i）和第 j (1 \le j \le M) 个身体零件（重量为 b_j），需要满足 a_i \le b_j。

如果能够形成至少 K 个满足条件的配对，则输出 Yes，否则输出 No。

解题思路

• 将 A 序列排序和 B 序列排序后，可以用两个指针标记它。
• 一个标记 A 序列（l 指针），一个标记 B 序列（r 指针）。
• 当满足要求，指针 l 和 r 往右跳一格。
• 不然，就是身体部件重量不够，r 往右跳一格。

优化思路

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

代码实现

方法一：标准双指针

#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 老师的代码再次优化而来。

#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 ;
}