能力组队

2024-07-08 13:12| 来源: 网络整理| 查看: 265

题目来自于博主算法大师的专栏：最新华为OD机试C卷+AB卷+OJ（C++JavaJSPy） https://blog.csdn.net/banxia_frontend/category_12225173.html

题目

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

输入

第一行代表总人数，范围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 思路

解题思路：

读取数据：

首先，从输入中读取总人数 count。然后，用数组 capacity[] 存储每个人的能力值。接着，读取团队要求的最低能力值 n。

排序能力值数组：

使用 qsort() 函数对 capacity[] 数组进行升序排序。这样可以确保在后续计算过程中，较小的能力值会优先考虑与其他元素组成队伍。

统计一人组队的数量：

初始化符合要求的团队数量 num 为0。遍历排序后的 capacity[] 数组，如果某个人的能力值大于等于 n，则说明他/她可以独立组成一支队伍，将 num 加一。

寻找两人组队的情况：

使用双指针法，初始化左指针 i 为0，右指针 j 为数组最后一个可能与 i 组队的人的位置（即 count - num - 1）。当 i < j 时，在每轮循环中判断 capacity[i] 和 capacity[j] 的和是否大于等于 n，若是，则表示这两个人可以组成一个满足要求的团队，将 num 加一，并移动左右指针；若不是，则只移动左指针 i。

输出结果：

循环结束后，num 即为最多可以派出的符合要求的团队数量，将其输出。代码 #include #include // 自定义比较函数，用于对数组进行排序 int cmp(const void *a, const void *b) { // 返回 a 元素减去 b 元素的差值，实现升序排序 return *(int *)a - *(int *)b; } int main() { int count; // 读取总人数 scanf("%d", &count); // 定义一个整数数组存储每个人的能力值 int capacity[count]; for (int i = 0; i // 遍历数组，统计能力值大于等于最低要求的人数 if (capacity[i] >= n) { num++; } } // 双指针法寻找可两人组队的情况 int i = 0; int j = count - num - 1; // j 指向可能与 i 组队的最右侧元素 while (i num++; // 符合条件队伍数量加一 i++; // 移动左指针 j--; // 移动右指针 } else { i++; // 若两人能力之和不满足条件，则只移动左指针 } } // 输出最多可以派出的团队数量 printf("%d", num); return 0; }

【本文地址】

公司简介

联系我们