2025 信奥赛 C++ 提高组 CSP-S 复赛真题及题解：员工招聘

员工招聘

题目描述

小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 ∼ n。每位应聘者有一个技能值 s_i。公司需要招聘 m 名员工，每个岗位对技能值有最低要求 r_j。若应聘者 i 的技能值 s_i ≥ r_j，则其可以胜任岗位 j。目标是最大化被成功招聘的人数。

解题思路

这是一个典型的贪心匹配问题。为了使招聘人数最大化，我们应该优先满足要求较低的岗位，或者让技能最高的应聘者去满足要求最高的岗位。这里采用排序后双指针或贪心的策略。

1. 将应聘者按技能值从小到大排序。
2. 将岗位要求从小到大排序。
3. 遍历岗位要求，尝试用当前技能最低的合格应聘者填补。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    
    vector<int> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    
    vector<int> r(m);
    for (int i = 0; i < m; ++i) cin >> r[i];

    sort(s.begin(), s.end());
    sort(r.begin(), r.end());

    int ans = 0;
    int ptr = 0;
    for (int i = 0; i < m && ptr < n; ++i) {
        if (s[ptr] >= r[i]) {
            ans++;
            ptr++;
        } else {
            // 当前应聘者技能不足，尝试下一个更高技能的
            ptr++;
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N log N + M log M)，主要消耗在排序上。
• 空间复杂度：O(N + M)，用于存储输入数据。