NC204859 组队

题目

题目描述

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

输入描述

第一行一个整数 \(T\)，表示案例组数。每个案例有两行：第一行两个正整数 \(n,k\) ，表示人的数量。

第二行 \(n\) 个以空格分隔的整数 \(a_i\) ，表示每个人的能力值。

输出描述

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

示例1

输入

输出

说明

选择能力值为 \(3,5,63,5,63,5,6\) 或者 \(5,6,85,6,85,6,8\)

备注

\(T \leq 10\)

\(1 \leq n \leq 2e5, 1 \leq k \leq 1e9\)

\(1 \leq a_i \leq 1e9\)

题解

思路

知识点：枚举，贪心。

注意到任意两人数值差不能大于 \(k\) ，因此考虑先按从小到大排序，枚举左端点和右端点，在符合右端点减左端点数值小于等于 \(k\) 的情况下加人数，其答案具有单调性，即左端点改变右端点不需要回撤，可以用尺取法。

时间复杂度 \(O(Tn \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

using namespace std;

int a[200007];

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t;

    cin >> t;

    while (t--) {

        int n, k;

        cin >> n >> k;

        for (int i = 0;i < n;i++) cin >> a[i];

        sort(a, a + n);

        int ans = 0;

        int l = 0, r = 0;

        while (l < n) {

            while (r < n && a[r] - a[l] <= k) r++;

            ans = max(ans, r - l);

            l++;

        }

        cout << ans << '\n';

    }

    return 0;

}

巴特西

NC204859 组队

NC204859 组队

题目

题解

思路

代码

最新文章

热门文章