华为OD统一考试 - 求最多可以派出多少支团队

题目描述

用数组代表每个人的能力，一个比赛活动要求参赛团队的最低能力值为N，每个团队可以由1人或者2人组成，且1个人只能参加1个团队，计算出最多可以派出多少只符合要求的团队。

输入描述

• 第一行代表总人数，范围1-500000
• 第二行数组代表每个人的能力数组大小，范围1-500000元素取值，范围1-500000
• 第三行数值为团队要求的最低能力值，范围1-500000

输出描述

最多可以派出的团队数量

用例

题目解析

本题要求最多的组队，而组队要求是：

• 可以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