目錄

?牛客.空調遙控

二分查找

牛客.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();}
}