题解：AT_abc431_c [ABC431C] Robot Factory

说在前面

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

题目分析

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

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

假设现在我们要匹配的头是 $i$ ，目前在第 $j$ 个身体；
我们不断地移动 $j$ ，直到能组成机器人，就把计数器加一；
$i$ 加一， $j$ 加一。重复这个过程，直到 $i > n$ 或者 $j > m$ 。

什么！你问我为什么这样做是对的？~~（用手）~~ 是因为我们的重量（

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

需要加一，因为一个不能重复用。

赛时代码

CPP

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

说在后面

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

题解：AT_abc431_c [ABC431C] Robot Factory

文章操作

说在前面

题目分析

注意事项：

赛时代码

说在后面

相关推荐

评论

题解：AT_abc431_c [ABC431C] Robot Factory