目录
牛客.空调遥控
枚举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 6
Arrays.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 6
Arrays.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和气球（数学问题)
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();
}
}