《从入门到精通：蓝桥杯编程大赛知识点全攻略》（五）-数的三次方根、机器人跳跃问题、四平方和
本博客将详细探讨如何通过二分查找算法来解决这几个经典问题。通过几个实际的例子，我们将展示如何在这些问题中灵活应用二分查找，优化计算过程，并在面对大数据量时保持高效性。
目录
前言
数的三次方根
算法思路
代码如下
机器人跳跃问题
算法思路
代码如下
四平方和
算法思路
代码如下
总结
前言
本博客将详细探讨如何通过二分查找算法来解决这几个经典问题。通过几个实际的例子，我们将展示如何在这些问题中灵活应用二分查找，优化计算过程，并在面对大数据量时保持高效性。
数的三次方根
给定一个浮点数 n，求它的三次方根。
输入格式
共一行，包含一个浮点数 n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00输出样例：
10.000000算法思路
这道题题很多思路。 这次主要通过二分来进行处理，锻加强二分的练习。设置两个double类型变量lleft = -10000，right = 10000；取中间值mid，当mid * mid * mid >= x的时候，说明右区间的值太大，在[left,mid]中寻找。如果mid * mid * mid < x，说明需要在(mid,right]区间里面找，最后的答案输出left或者right都可。（注意题目精度，结果要6位小数，那么循环判断的时候增加两位精度即1e-8即可）
代码如下
import java.io.*;
public class Main {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
public static void main(String[] args)throws Exception {
double x = nextDouble();
double left = -10000;
double right = 10000;
while (right - left > 1e-8) { //1e-8表示的题目精度，随题目变化而变化，一般比所求答案高两个精度
double mid = (left + right) / 2;
if(mid * mid * mid >= x){
right = mid;
}else {
left = mid;
}
}
pw.printf("%.6f", right);
pw.flush();
}
public static double nextDouble()throws Exception{
st.nextToken();
return (double)st.nval;
}
}
机器人跳跃问题
机器人正在玩一个古老的基于 DOS 的游戏。
游戏中有 N+1 座建筑——从 0到 N 编号，从左到右排列。
编号为 0 的建筑高度为 0个单位，编号为 i 的建筑高度为 H(i) 个单位。
起初，机器人在编号为 0 的建筑处。
每一步，它跳到下一个（右边）建筑。
假设机器人在第 k 个建筑，且它现在的能量值是 E，下一步它将跳到第 k+1个建筑。
如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到 E−H(k+1)的能量值。
游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。
现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？
输入格式
第一行输入整数 N。
第二行是 N 个空格分隔的整数，H(1),H(2),…,H(N) 代表建筑物的高度。
输出格式
输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。
数据范围
1≤N,H(i)≤10^5
输入样例1：
5
3 4 3 2 4算法思路
根据图示的推论 可知，其实无论哪一种情况最后E能量的变化都为2*E-h(i)；与此同时当我们发现，如果E满足题意，那么E1 >= E，那么E1也是满足题意的。此时答案E就具有的单调性。
根据图示的推论，那么我们就知道答案E的最大值一定不超过100000，最小值大于等于0；可以用二分的方式来进行计算。
用整型数组arr记录每个建筑的能量值，用整型变量n来记录建筑数，左边界left = 0；右边界right = 100000；当left < right时，开始循环，找到中间值mid = (left + right) / 2；然后检查此时的mid值是否符合要求；
检查函数check，传过来的值E能量，然后从1遍历到n，计算e = 2 * e - arr[i]；然后判断此时的e是否小于0，小于0直接不符合要求，返回false；当e >= 100000时，相当于满足题意了，一定成功可以提前返回true。循环结束时，返回true，表示满足题意。
当判断mid为true时说明此时的区间(mid,right]区间内，一定是E的值比mid大，最后答案要的是mid的最小值，说明右区间不可能存在，故右边界左移即right = mid；当mid不合格，说明区间[left,mid]中所有的E都不符合题意，故正确答案一定在右区间，所以左区间右移即left = mid + 1；最后输出left即为最后的答案。
代码如下
import java.io.*;
public class Main {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static int N = 100010;
static int[] arr = new int[N];
static int n;
public static void main(String[] args)throws Exception {
n = nextInt();
for (int i = 1; i <= n; i++) {
arr[i] = nextInt();
}
int left = 0;
int right =100000;
while (left < right) {
int mid = (left + right) / 2;
if(check(mid)){
right = mid;
}else {
left = mid + 1;
}
}
pw.println(left);
pw.flush();
}
public static boolean check(int e){
for(int i = 1;i <= n;i++){
e = e * 2 - arr[i];
//只要大于等于e的最大值，那么必然符合条件
if(e >= 100000){
return true;
}
if(e < 0){
return false;
}
}
return true;
}
public static int nextInt()throws Exception {
st.nextToken();
return (int) st.nval;
}
}
四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
输入格式
输入一个正整数 N。
输出格式
输出4个非负整数，按从小到大排序，中间用空格分开。
数据范围
0<N<5*10^6
输入样例：
5输出样例：
0 0 1 2算法思路
暴力做法直接枚举前3个数a、b、c，最后一个d可以直接算，因为d是算出来的，可能为小数，还需判断一下
，当条件成立是就是最后的答案。（但这道题枚举3层循环会超时。）
二分优化做法。
先枚举所有c、d的情况，然后将c、d、c*c+d*d 3个值存起来，再去枚举a、b的情况，然后将 t = n - a * a - b * b与对应的c*c+d*d做对比，找出正确的答案。
引入整型变量n才存储最后的结果，用两层循环来枚举c和d，用一类内部类Sum来存储c、d和sum（存储c*c+d*d）；每枚举一个c和d，将3个值存储list列表。循环结束后，按照宿命从小到大，当sum相同时按照c从小到大，当c相同时按照d从小到大。
然后再用两次循环枚举a和b，用整型变量t来存储n - a * a - b * b；用二分来查找，左边界left0，右边界list列表的长度-1；当列表list中的下标为mid的sum >= t，此时说明答案在左区间，此时右边界左移right = mid；当list中的下标为mid的sum < t，说明答案在右区间且不包括下标为mid，所以左区间右移即left = mid + 1；最后list中的下标为left的sum等于t时，此时得到的a、b、c、d就是最后的答案。
代码如下
暴力做法
public class 四平方和 {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static int n;
public static void main(String[] args)throws Exception {
n = nextInt();
for(int a = 0; a * a <= n;a++){
for(int b = 0;b * b + a * a <= n;b++){
for(int c = b; c * c + b * b + a * a <= n;c++ ){
int t = n - a * a - b * b - c * c;
int d =(int) Math.sqrt(t);
if(d * d == t){
pw.println(a+" "+b+" "+c+" "+d);
pw.flush();
return;
}
}
}
}
}
public static int nextInt()throws Exception {
st.nextToken();
return (int)st.nval;
}二分优化
import java.io.*;
import java.util.*;
public class Main {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer st = new StreamTokenizer(br);
static List<Sum> list = new ArrayList();
static int n;
public static void main(String[] args)throws Exception {
n = nextInt();
for(int c = 0; c * c <= n;c++){
for(int d = c;c * c + d * d <= n;d++){
list.add(new Sum(c * c + d * d,c,d));
}
}
//字典序排序 lambda表达式
list.sort((sum1,sum2)->{
if(sum1.sum != sum2.sum) return sum1.sum - sum2.sum;
if(sum1.c != sum2.c) return sum1.c - sum2.c;
return sum1.d - sum2.d;
});
for(int a = 0; a * a <= n;a++){
for(int b = a;b * b + a * a <= n;b++){
int t = n - a * a -b * b;
int left = 0;
int right = list.size() - 1;
while(left < right){
int mid = (left + right)/2;
if(list.get(mid).sum >= t){
right = mid;
}else {
left = mid + 1;
}
}
if(list.get(left).sum == t){
pw.println(a+" "+b+" "+list.get(left).c+" "+list.get(left).d);
pw.flush();
return;
}
}
}
pw.flush();
}
public static int nextInt()throws Exception {
st.nextToken();
return (int)st.nval;
}
}
class Sum{
int sum;//c^2 + d^2 = sum
int c;
int d;
public Sum(int sum, int c, int d) {
this.sum = sum;
this.c = c;
this.d = d;
}
}
总结
二分查找不仅仅是一种简单的查找方法，它在很多复杂问题中都有着非常广泛的应用。掌握二分查找的技巧，将帮助我们在面对各种挑战时，能够快速并准确地找到答案。