最新华为OD机试真题-团队派遣(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 团队派遣(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

✨ 团队派遣

问题描述

K小姐是一家公司的人力资源经理，她需要从公司的 名员工中选出一些人组成团队，参加一个比赛活动。每个员工都有一个能力值，一个团队的能力值等于所有成员能力值的总和。

活动要求参赛团队的能力值不能小于 。每个团队可以由 人或 人组成，且每个人只能参加 个团队。

请你帮助K小姐计算最多可以派出多少支符合要求的团队。

输入格式

第一行包含一个正整数 表示员工人数。

第二行包含 个正整数，第 个数 表示第 名员工的能力值。

第三行包含一个数 ，表示团队能力值要求。

输出格式

输出一个整数，表示最多可以派出的团队数量。

样例输入

5
3 1 5 7 9
8

样例输出

3

数据范围

题解

我们可以先将员工按照能力值从小到大排序，然后用双指针的方法来解决这个问题。

初始时，左右指针分别指向序列的两端。如果右指针指向的员工的能力值大于等于 ，那么他自己可以组成一个团队，右指针左移，团队数加 。否则，如果左右指针指向的两个员工的能力值之和大于等于 ，那么他们两个可以组成一个团队，左右指针分别向中间移动，团队数加 。如果不满足以上两种情况，左指针右移。

当左右指针相遇时，如果指针指向的员工能力值大于等于 ，那么他自己可以组成一个团队，团队数加 。

最后输出团队数即可。

参考代码

• Python

n = int(input())
a = list(map(int, input().split()))
x = int(input())
a.sort()  # 按能力值排序

l, r = 0, n - 1
cnt = 0

while l < r:
    if a[r] >= x:  # 右指针员工自己可以组成一队
        r -= 1
        cnt += 1
    elif a[l] + a[r] >= x:  # 左右指针员工可以组成一队
        l += 1
        r -= 1
        cnt += 1
    else:
        l += 1

if l == r and a[l] >= x:  # 剩下一个员工且能力值足够
    cnt += 1

print(cnt)

• Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int x = sc.nextInt();
        Arrays.sort(a);  // 按能力值排序
        
        int l = 0, r = n - 1;
        int cnt = 0;
        
        while (l < r) {
            if (a[r] >= x) {  // 右指针员工自己可以组成一队
                r--;
                cnt++;
            } else if (a[l] + a[r] >= x) {  // 左右指针员工可以组成一队
                l++;
                r--;
                cnt++;
            } else {
                l++;
            }
        }
        
        if (l == r && a[l] >= x) {  // 剩下一个员工且能力值足够
            cnt++;
        }
        
        System.out.println(cnt);
    }
}

• Cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> x;
    
    sort(a, a + n);  // 按能力值排序
    
    int l = 0, r = n - 1;
    int cnt = 0;
    
    while (l < r) {
        if (a[r] >= x) {  // 右指针员工自己可以组成一队
            r--;
            cnt++;
        } else if (a[l] + a[r] >= x) {  // 左右指针员工可以组成一队
            l++;
            r--;
            cnt++;
        } else {
            l++;
        }
    }
    
    if (l == r && a[l] >= x) {  // 剩下一个员工且能力值足够
        cnt++;
    }
    
    cout << cnt << endl;
    
    return 0;
}