1 条题解

  • 0
    @ 2026-2-6 14:56:59
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] 全局变量定义
    int n, k;               // n:选手总数量;k:每组允许的最大身高差
    int arr[50100];         // 存储所有选手的身高(下标1~n)
    
    int main() {
        // [2] 输入处理:读取选手数量和身高差上限
        cin >> n >> k;
        // [3] 读取每位选手的身高
        for (int i = 1; i <= n; i++) cin >> arr[i];
    
        // [4] 排序:将身高升序排列,为双指针找合法区间做准备
        sort(arr + 1, arr + n + 1);
    
        // [5] 预处理left数组:left[i]表示前i个选手中,单组的最大人数
        vector<int> left(n + 1);
        int j = 1;  // 双指针j:维护以i为终点的合法区间的最小起点
        for (int i = 1; i <= n; i++) {  // i为区间终点,寻找合法起点j
            // 移动j,直到arr[i]-arr[j] <=k(区间内身高差合法)
            while (j <= n && arr[i] - arr[j] > k) {
                j++;
            }
            // 更新left[i]:取当前区间长度和前i-1个的最大值
            left[i] = max(i - j + 1, left[i - 1]);
        }
    
        // [6] 预处理right数组:right[i]表示从i到n的选手中,单组的最大人数
        vector<int> right(n + 2);
        j = n;  // 双指针j:维护以i为起点的合法区间的最大终点
        for (int i = n; i >= 1; i--) {  // i为区间起点,寻找合法终点j
            // 移动j,直到arr[j]-arr[i] <=k(区间内身高差合法)
            while (j >= 1 && arr[j] - arr[i] > k) {
                j--;
            }
            // 更新right[i]:取当前区间长度和i+1到n的最大值
            right[i] = max(j - i + 1, right[i + 1]);
        }
    
        // [7] 计算最多两组的最大人数
        int max_len = left[n];  // 初始化为单组的最大人数(覆盖无需分组的场景)
        // 遍历所有分割点i,计算[1,i]和[i+1,n]两组的人数和,取最大值
        for (int i = 1; i <= n - 1; i++) {
            max_len = max(max_len, left[i] + right[i + 1]);
        }
    
        // [8] 输出结果
        cout << max_len;
    
        return 0;
    }
    

    信息

    ID
    1328
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者