一、分析题目
1、滑动窗口
先排序，然后维护窗口内最大值与最小值的差在 2 * p 之间（max - min）。
2、二分查找
先排序，然后枚举所有的温度，⼆分出符合要求的学生区间，然后统计个数。
二、代码
1、滑动窗口（推荐）
//值得学习的代码 //O(NlogN) #include <iostream> #include <algorithm> using namespace std; const int N = 1e6 + 10; int n, p; int arr[N]; int main() { cin >> n >> p; for(int i = 0; i < n; i++) cin >> arr[i]; sort(arr, arr + n); int ret = 0, left = 0, right = 0; p *= 2; while(right < n) { while(arr[right] - arr[left] > p) { left++; } ret = max(ret, right - left + 1); right++; } cout << ret << endl; return 0; }
2、二分查找
#include <iostream> #include <algorithm> using namespace std; const int N=1e6+10; int a[N]; int main() { int n, p; cin >> n >> p; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a+n); int res=0; int mini=a[0], maxi=a[n-1]; for(int k=mini; k<=maxi; k++) { int target=max(k-p, 1); int left=0, right=n-1; while(left<right) { int mid=left+(right-left)/2; if(a[mid]>=target) right=mid; else left=mid+1; } int l=left; left=0, right=n-1; target=k+p; while(left<right) { int mid=left+(right-left+1)/2; if(a[mid]<=target) left=mid; else right=mid-1; } res=max(res, right-l+1); } cout << res << endl; return 0; }
三、反思与改进
我只想到了暴力解法，显示排序，然后确定 K 的范围是在数组 a 中的最大和最小值之间，接着看看有多少学生符合要求。因为是取绝对值，所以我就想着从中间值开始向两边遍历，遇到不符合要求的就可以直接 break 了，然后在所有情况里面取最大值即可，但这样做肯定超过数据范围。在看有多少学生符合要求这里可以进行优化，利用二分来确定符合要求学生的范围，再通过范围即可得出数量。
如果采用滑动窗口的话，这道题的核心就在于需要控制最大值与最小值的差在 2 * p 之间，这个点没有想到。
