题解：AT_abc431_c [ABC431C] Robot Factory

zcq_qwq · 2025-11-17 15:35:46 · 题解

说在前面

前置芝士：双指针、排序、贪心。

题目分析

既然要判断满足满足条件，那么就要使得能被组成的机器人最多，我们必须拿最小的头去组装最小的合法的身子，这样一定是最优的。为什么呢？假设你拿最小的头去组装大的身子，那后面来了一个更大的头，你就没办法组装了，答案一定不会更优。

我们先排序：然后这个过程使用双指针实现：

• 假设现在我们要匹配的头是 i，目前在第 j 个身体；
• 我们不断地移动 j，直到能组成机器人，就把计数器加一；

什么！你问我为什么这样做是对的？（用手） 是因为我们的重量（H _ {i} 和 B _ {i}）均为单调不减，你往后走会越来越小，所以我们的 j 指针始终只往前移。

时间复杂度 O(m)。

什么！你又问我为什么不是 O(nm)？考虑到 j 只往前移，最多从 1 到 m，也就是说，假设对于每个 i，j 往前移 x _ i 位，那么时间复杂度最多是 \sum _ {i = 1} ^ {n} x _ i \le m，i 的作用相当于 \sum。

注意事项：

每次找到匹配的以后 j 需要加一，因为一个不能重复用。

赛时代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

namespace zcq_qwq {
    const int N = 2e5 + 5;

    int n, m, k;

    int a[N], b[N];

    void main() {
        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);
        // cout << n << " " << m << endl;
        int l = 1, r = 1, ans = 0;
        while (l <= n) {
            while (r <= m && b[r] < a[l]) {
                r++;
            }
            if (r > m) {
                break;
            }
            ans++;
            r++;
            l++;
        }
        // cout << ans << endl;
        if (ans < k) {
            cout << "No";
        } else {
            cout << "Yes";
        }
    }
}

signed main() {
    zcq_qwq::main();
    return 0;
}

说在后面

若代码、思路讲解有误，欢迎提出。