牛客.空调遥控

a暴力枚举    n^2

自己去排序

a[0]-a[n-1]的所有温度，看看多少个学生符合要求。

[1,5,3,2,4,6]

枚举所有温度（没法优化),(看看多少个学生符合要求->这一步优化）

假如温度等于3 那么需要看[1,5]的话即可。

如果有序，那么就会特别快了。只需要快速查找【1，5】两个端点就OK了

解法2:

排序+二分(二分两个端点)N*logn+N*logN

解法3:N*1ogN +O(N)(滑动窗口)

滑动窗口(最大值与最小值<=2p，维持区间)

[1 2 3 4 5 6]

假如调出的数最大值与最小值

一个t->[t-p,t+p],此时最大值减去最小值一定是小于等于两倍的p

max-min<=2p   最大值减去最小值

[left,right] right++,(我们发现right不用动)

 Scanner in=new Scanner(System.in);
      int n=in.nextInt();
      int p=in.nextInt();
      int[]a=new int[n];
      for(int i=0;i<n;i++){
          a[i]=in.nextInt();
      }
       Arrays.sort(a);
      int left=0;
      int right=0;
      int ret=0;
      while(right<n){
          while(a[right]-a[left]>2*p){
              left++;
          }
          ret=Math.max(ret,right-left+1);
              right++;
      }
      System.out.print(ret);

二分算法（回顾二分的细节) 

二分是最容易写错死循环的，细节超多，所以我又回顾了一遍，这个很难的细节

import java.util.*;
public class Main {
  public  static void main(String[]args){
       Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int p = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a);
        int ret = 0;

        for (int i = a[0]; i <= a[n - 1]; i++) {
            int target = Math.max(i - p, 1);
            int left = 0;
            int 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;
            target = i + p;
            left = 0;
            right = n - 1;
            while (left < right) {
                int mid = left + (right - left+1) / 2;
                if (a[mid] <= target) {
                    left = mid;
                } else
                    right = mid-1;
            }
            ret = Math.max(ret, right - l + 1);
        }
        System.out.print(ret);
  }  
}

回顾二分，（二分是选择中间的点，时间复杂度最低）

定义left,right ,mid=中间的中点

1.朴素二分模版 -easy但是

2.查找左边界模版。-万能细节多

3.查找右边界模版 -万能细节多