Skip to content

牛客网 NC204859 组队#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: C/C++ 1秒，其他语言2秒

Memory Limit: C/C++ 262144K，其他语言524288K

1.2. Problem Description#

你的团队中有 个人，每个人有一个能力值 ，现在需要选择若干个人组成一个团队去参加比赛，由于比赛的规则限制，一个团队里面任意两个人能力的差值必须要小于等于 ，为了让更多的人有参加比赛的机会，你最多能选择多少个人参加比赛？

1.3. Input#

第一行一个整数 ，表示案例组数。每个案例有两行：第一行两个正整数 ，表示人的数量。第二行 个以空格分隔的整数 ，表示每个人的能力值。

1.4. Output#

每个案例输出一行，表示可以参加比赛的最多人数。

1.5. Sample Input#

1
5 3
8 3 5 1 6

1.6. Sample Output#

3

1.7. Note#

选择能力值为 或 。

1.8. Source#

牛客网 NC204859 组队

2. 解读#

使用滑动窗口进行计算。

先对数组从小到大进行排序，如果 区间内的数都满足 ，则 ，否则 ，每滑动一次计算一次 ，取所有情况的最大值即可。

3. 代码#

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

const int num = 2e5 + 1;
long long list[num];

int main(){
    long long t, n, k, ans, buffer, left, right;
    scanf("%lld", &t);
    for(int j = 0; j < t; j++){
        // 初始化
        memset(list, 0, sizeof(list));
        ans = 0;
        left = 0;
        right = 1;
        // 输入
        scanf("%lld %lld", &n, &k);
        for(long long i = 0; i < n; i++){
            scanf("%lld", &list[i]);
        }
        // 排序
        sort(list, list + n);
        // 计算
        while(right < n){
            // 当右端点为n时结束循环
            if(list[right] - list[left] <= k){
                // 如果满足条件，最大值和最小值差值小于等于k
                // 右端点右移
                right++;
            }else{
                // 不满足条件，左端点右移
                left++;
            }
            ans = max(ans, right - left);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

二维码

Back to top