目录

 牛客.空调遥控

二分查找

牛客.kotori和气球（数学问题)

力扣.二叉树的最大路径和

牛客.主持人调度(二)

---

 牛客.空调遥控

枚举n个空调之后，使数组有序，左右下标，用二分查找，然后一个求

长度就好

二分查找

/二分理解，+k-p<=a[i]      ||a[i]<=k+p

然后剩下的就是二分美学，细节很多

假如我们求的是区间的话，是要注意left<right，然后看，他的求mid的条件，求的是左端点

假如left+(right-left+1)/2 ，求的是右端点

import java.util.*;
import java.io.*;
public class Main{public static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in=new Read();public static void main(String[] args) throws IOException {Read in = new Read();int n=in.nextInt();int p=in.nextInt();int[]a=new int[n];//  a[i]<=p+k  ||  k-p <=a[i]for(int i=0;i<n;i++){a[i]=in.nextInt();}int ret=0;// 1 2 3 4 5 6Arrays.sort(a);for(int i=0;i<n;i++){int k=a[i];//以当前值为k,二分 求的一个大于等于，一个小于等于int left=0;int right=n-1;//比如求左端点 大于等于左边while(left<right){int mid=left+(right-left)/2;//二分理解，+k-p<=a[i]if(a[mid]>=k-p){right=mid;}else{left=mid+1;}}int nowLeft=left;left=0;right=n-1;while(left<right){int mid=left+(right-left+1)/2;if(a[mid]<=p+k){left=mid;}else{right=mid-1;}}ret=Math.max(ret,right-nowLeft+1);}System.out.print(ret);}
}class Read{public StringTokenizer st=new StringTokenizer("");public BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));public String next()throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public String nextLine()throws IOException{return bf.readLine();}public int nextInt()throws IOException{return Integer.parseInt(next());}public long nextLong()throws IOException{return Long.parseLong(next());}    
}

   //【k-p,k+p】      换句话说，最大值-最小值在2p区间内,因此选择一个滑动窗口

import java.util.*;
import java.io.*;
public class Main{public static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in=new Read();public static void main(String[] args) throws IOException {Read in = new Read();int n=in.nextInt();int p=in.nextInt();int[]a=new int[n];//  a[i]<=p+k  ||  k-p <=a[i]for(int i=0;i<n;i++){a[i]=in.nextInt();}int ret=0;// 1 2 3 4 5 6Arrays.sort(a);//以当前值为k,二分 求的一个大于等于，一个小于等于int left=0;int right=0;while(right<n){while(a[right]-a[left]>2*p){left++;}ret=Math.max(ret,right-left+1);right++;}System.out.print(ret);}
}class Read{public StringTokenizer st=new StringTokenizer("");public BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));public String next()throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public String nextLine()throws IOException{return bf.readLine();}public int nextInt()throws IOException{return Integer.parseInt(next());}public long nextLong()throws IOException{return Long.parseLong(next());}    
}

kotori和气球

牛客.kotori和气球（数学问题)

6中气球摆5个位置，第一个没有限制，有几种几种和

6 5 5（只要和前面的不同就行) 5 5      这我怎么想不出来？ 狠狠压麻袋住了

n*(n-1)*(n-1) xxx 一共m-1个n-1 ，感觉最近做模拟做的有点傻，都不会数学了。

import java.util.*;
public class Main{public static void main(String[]args){Scanner in=new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();int p=109;long count=1;for(int i=0;i<m-1;i++){count=count*(n-1)%p;      }System.out.print(count*n%p);}
}

力扣.二叉树的最大路径和

题没啥参考价值，直接看样例，

左子树是一个，以左子树为跟的最大单链和，

右子树也一样，以右子树为跟的最大单链和。

    int max = -100000;
public int maxPathSum(TreeNode root) {if (root == null) return 0;maxSum(root);return max;}public int maxSum(TreeNode root) {if (root == null) return 0;int left = Math.max(maxSum(root.left),0);int right =Math.max(maxSum(root.right),0);max = Math.max(left + right + root.val, max);return Math.max(left, right) + root.val;}

牛客.主持人调度(二)

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 计算成功举办活动需要多少名主持人* @param n int整型 有n个活动* @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间* @return int整型*/public int minmumNumberOfHost(int n, int[][] a) {Arrays.sort(a, (m, k) -> {if (m[0] == k[0]) return Integer.compare(m[1],k[1]);return Integer.compare(m[0] , k[0]);});//全程升序PriorityQueue <Integer>q=new PriorityQueue<>();for (int i = 0; i < n; i++) {//从当前位置开始计算，看看有几个冲突，取冲突的最大值，就是需要的主持人个数//存右边的边界值if(q.isEmpty())q.add(a[i][1]);else{//[-6,-1][-4,-3][-2,2][1,6][1,7] [7,8]if(q.peek()<=a[i][0]){//能连接，我就poll()q.poll();}q.add(a[i][1]);                  }}return q.size();}
}