1 条题解
-
0
#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; }
- 1
信息
- ID
- 1328
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者