华为OD统一考试 - 求最多可以派出多少支团队
题目描述
用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，每个团队可以由1人或者2人组成，且1个人只能参加1个团队，计算出最多可以派出多少只符合要求的团队。
输入描述
- 第一行代表总人数，范围1-500000
- 第二行数组代表每个人的能力数组大小，范围1-500000元素取值，范围1-500000
- 第三行数值为团队要求的最低能力值，范围1-500000
输出描述
最多可以派出的团队数量
用例
输入 |
5 3 1 5 7 9 8 |
输出 |
3 |
说明 |
说明 3、5组成一队 1、7一队 9自己一队 输出3 |
输入 |
7 3 1 5 7 9 2 6 8 |
输出 |
4 |
说明 |
3、5组成一队，1、7一队，9自己一队，2、6一队，输出4 |
输入 |
3 1 1 9 8 |
输出 |
1 |
说明 |
9自己一队，输出1 |
题目解析
本题要求最多的组队，而组队要求是：
- 可以1人组队，也可以2人组队
- 团队的能力值之和需要大于等于最低能力minCap要求
因此，为了组更多队伍，我们应该尽量让单人组队，即：
- 需要将能力值大于等于minCap的筛选出来，单人组队
然后剩余的人，按照能力值升序排序，定义L,R指针，初始时L=0，R=k-1，k是剩余人总数
接着尝试L，R进行组队：
- 如果L，R两人的能力之和大于等于minCap，则组队成功，L++，R--
- 否则，说明L无法和任何人组队，因为R已经是当前最高能力的人，L无法和R组队，则也意味着无法和能力值比R低的人组队，因此L++
在上面过程中，计算出组队个数作为题解。
import Foundation
func ODTest_35() {
print("第一行代表总人数，范围1-500000")
let
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2024华为OD机试卷题 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库，帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。
米哈游公司福利 1636人发布
查看21道真题和解析