蓝桥杯冲刺题单--二分

二分

知识点

二分：
1.序列二分：在序列中查找（不怎么考，会比较难？）
序列二分应用的序列必须是递增或递减，但可以非严格
只要r是mid-1，就对应mid=（l+r+1）/2
2.答案二分：最值
答案二分更重要的是思路，要自己可以二分的点，一般先写暴力，再将其转为二分。
3.浮点数二分：连续性

1.1序列二分模板题–蓝桥18492

模板题目

package erfen;import java.util.Scanner;public class Test1 {static int N = 100010;static int n, q;static int[] a = new int[N];//找到等于x的最左边的数的下标static int getL(int l, int r, int x) {while (l < r) {int mid = l + r >> 1;//右移1表示除以2if (a[mid] >= x) r = mid;else l = mid + 1;}if (a[l] == x)return l;//返回下标elsereturn -1;//不存在}//找到等于x的最右边的数的下标static int getR(int l, int r, int x) {while (l < r) {int mid = l + r + 1 >> 1;//右移1表示除以2if (a[mid] <= x) l = mid;else r = mid - 1;}if (a[l] == x)return l;//返回下标elsereturn -1;//不存在}//找到大于等于x的第一个数的下标static int lower_bound(int l, int r, int x) {while (l < r) {int mid = l + r >> 1;//右移1表示除以2if (a[mid] >= x) r = mid;else l = mid + 1;}if (a[l] >= x)return l;//返回下标elsereturn -1;//不存在}//找到大于x的第一个数的下标static int upper_bound(int l, int r, int x) {while (l < r) {int mid = l + r >> 1;//右移1表示除以2if (a[mid] > x) r = mid;else l = mid + 1;}if (a[l] > x)return l;//返回下标elsereturn -1;//不存在}//主逻辑函数static void solve() {Scanner sc = new Scanner(System.in);n = sc.nextInt();q = sc.nextInt();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}for (int i = 0; i < q; i++) {int op = sc.nextInt();int l = sc.nextInt();int r = sc.nextInt();int x = sc.nextInt();if (op == 1) {System.out.println(getL(l, r, x));} else if (op == 2) {System.out.println(getR(l, r, x));} else if (op == 3) {System.out.println(lower_bound(l, r, x));} else if (op == 4) {System.out.println(upper_bound(l, r, x));}}}public static void main(String[] args) {solve();}
}

1.2最大通过数–蓝桥3346–前缀和+二分

本题利用了前缀和和二分
思想很重要，首先枚举左边，再在里面枚举右边的通过数。
先写暴力然后就很容易写二分。
注意数值范围

暴力

package erfen;import java.util.Scanner;public class Test2 {static int N = 200010;static int m,n;static long k;static long[] a = new long[N];static long[] b = new long[N];//主逻辑函数static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextLong();a[i] = a[i - 1] + a[i];//计算前缀和}for (int i = 1; i <= m; i++) {b[i] = sc.nextLong();b[i] = b[i - 1] + b[i];//计算前缀和}int ans = 0;for (int i = 0; i <= n; i++) {//循环左边if(a[i] > k) break;//a[0]为0，所以无需担心左边为0没有遍历右边long x = k - a[i];//左边可通过i关for (int j = 0; j <= m; j++) {if(x >= b[j]){//右边可通过j关ans = Math.max(ans, i + j);}else{break;}}}System.out.println(ans);}public static void main(String[] args) {solve();}
}

二分

计算前缀和数组，它是递增的，可以应用二分
要二分就要找到单调的趋势，找到可以二分的点。

package erfen;import java.util.Scanner;public class Test2 {static int N = 200010;static int m,n;static long k;static long[] a = new long[N];static long[] b = new long[N];//主逻辑函数static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextLong();a[i] = a[i - 1] + a[i];//计算前缀和}for (int i = 1; i <= m; i++) {b[i] = sc.nextLong();b[i] = b[i - 1] + b[i];//计算前缀和}int ans = 0;for (int i = 0; i <= n; i++) {//枚举左边if(a[i] > k) break;//a[0]为0，所以无需担心左边为0没有遍历右边long x = k - a[i];//剩下的//二分第二个山洞,找到大于x的第一个数//因为是找大于x的第一个数，x可能是最后一个即m，所以r的取值要是m+1int l = 0, r = m + 1;while(l < r){int mid = l + r >> 1;if(b[mid] > x) r = mid;else l = mid + 1;}ans = Math.max(ans, i + l - 1);}System.out.println(ans);}public static void main(String[] args) {solve();}
}

1.3答案二分模板–https://hydro.ac/d/shallowdream/p/33

求最小的最大值，这题和后面那道数列分段一样，都是要求一个最值。
这个最值是自己进行枚举来得到的，这是一个重要的思路。
第二个就是本题的k次加一操作转换为了元素要达到max需要消耗多少k值，由此找到最小的max

暴力

package erfen;import java.util.Scanner;public class Test3 {static int N = 100010;static int n;static long k;static int[] a = new int[N];static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}//枚举最小值for (int i = 1; i <= 1e14; i++) {long t = k;//每次都要重新初始化for (int j = 1; j <= n; j++) {//循环数组每个元素看能否达到iif(a[j] < i){t = t -(i - a[j]);//a[j]需要(i - a[j])次加一操作才能达到i}//结束后进行判断if(t < 0){//当前数组某个元素不能达到i，那整个数组都不能达到iSystem.out.println(i - 1);return;//结束全部}}}}public static void main(String[] args) {solve();}
}

二分

找到可以二分的点：随着枚举的最大的最小值越大，t的值即剩余的k操作越来越少。

package erfen;import java.util.Scanner;public class Test3 {static int N = 100010;static int n;static long k;static int[] a = new int[N];//static boolean check(long m){long t = k;//每次都要重新初始化for (int j = 1; j <= n; j++) {//循环数组每个元素看能否达到mif(a[j] < m){t = t -(m - a[j]);//a[j]需要(m - a[j])次加一操作才能达到m}//结束后进行判断if(t < 0){//当前数组某个元素不能达到i，那整个数组都不能达到i/*System.out.println(i - 1);*/return false;//结束全部}}//整个循环结束，表示整个数组可以达到mreturn true;}static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();k = sc.nextLong();for (int i = 1; i <= n; i++) {a[i] = sc.nextInt();}//二分最大的最小值long l = 1;long r = (long)1e14;while(l < r){long mid = l + r + 1 >> 1;if(check(mid)) l = mid;//true，表示可以达到mid，但是这个mid不一定是最大的。所以让l=mid。else r = mid - 1;}System.out.println(l);}public static void main(String[] args) {solve();}
}