题解 | #组队#
组队
https://ac.nowcoder.com/acm/problem/204859
这是一个典型的排序+滑动窗口的问题。为了解决这个问题，我们需要按照能力值对所有人进行排序，然后使用一个滑动窗口来检测在能力值差不超过k的情况下能够包含的最大人数。
以下是解决此问题的步骤：
-
排序：首先对所有人的能力值进行非降序排序，这样可以确保我们在遍历过程中能够容易地检查相邻成员之间能力值的差是否满足条件。
-
初始化：设置两个指针，left和right，初始时都指向数组的第一个元素（即能力值最小的成员）。同时，设置一个变量max_count用于记录当前可以参加比赛的最多人数，初始化为1（至少一个人）。
-
滑动窗口扩展与收缩：
- 移动右指针 right 向右，每次移动都将当前人员纳入考虑范围，并检查当前窗口内（left 到 right 间）所有人的能力值是否满足最大差值不大于k的条件。如果满足，尝试增加 right 并更新 max_count。
- 当窗口内的能力值差超过k时，移动左指针 left 向右，缩小窗口，直到窗口内再次满足条件。这个过程保证了我们总是尝试包含尽可能多的、符合差值限制的人。
-
遍历结束：当右指针遍历完整个排序后的数组后，max_count将存储可以参加比赛的最多人数。
#include <iostream>
#include <vector>
#include <algorithm> // 用于std::sort
using namespace std;
// 定义函数maxTeamSize计算最多可以参加比赛的人数
int maxTeamSize(int n, int k, vector<int>& abilities) {
// Step 1: 对能力值进行排序
sort(abilities.begin(), abilities.end()); // 使用std::sort对abilities升序排序
// Step 2: 初始化双指针和计数器
int left = 0; // 左指针
int right = 0; // 右指针
int max_count = 1; // 至少一个人可以参加，所以初始值为1
// Step 3: 滑动窗口法处理
while (right < n) { // 遍历整个数组
// 如果当前窗口内的能力值差不超过k，则尝试扩大窗口
if (abilities[right] - abilities[left] <= k) {
// 更新最大可选人数，取当前窗口大小或已知最大值中的较大者
max_count = max(max_count, right - left + 1);
// 右指针向右移动，扩大窗口
right++;
} else {
// 如果窗口内的能力值差超过了k，缩小窗口，从左侧开始排除人
left++; // 左指针向右移动
}
}
// 返回最多可以参加比赛的人数
return max_count;
}
int main() {
// 示例输入
int t,x; // 测试用例数量
int n,k;// 人数和能力值差限制
cin>>t;
while(t--){
vector<int> abilities;// 能力值列表
abilities.clear();
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>x;
abilities.push_back(x);
}
// 调用函数并输出结果
cout << maxTeamSize(n, k, abilities) << endl;
}
return 0;
}
字节跳动公司氛围 606人发布
