《从入门到精通：蓝桥杯编程大赛知识点全攻略》（五）-数的三次方根、机器人跳跃问题、四平方和

本博客将详细探讨如何通过二分查找算法来解决这几个经典问题。通过几个实际的例子，我们将展示如何在这些问题中灵活应用二分查找，优化计算过程，并在面对大数据量时保持高效性。

前言

数的三次方根

算法思路

代码如下

机器人跳跃问题

算法思路

代码如下

四平方和

算法思路

代码如下

总结

前言

本博客将详细探讨如何通过二分查找算法来解决这几个经典问题。通过几个实际的例子，我们将展示如何在这些问题中灵活应用二分查找，优化计算过程，并在面对大数据量时保持高效性。

数的三次方根

给定一个浮点数 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 个数的平方和。

比如：

$5=0^{2}+0^{2}+1^{2}+2^{2}$

$7 = 1^{2}+1^{2}+1^{2}+2^{2}$

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

0≤a≤b≤c≤d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入格式

输入一个正整数 N。

输出格式

输出4个非负整数，按从小到大排序，中间用空格分开。

数据范围

0<N<5*10^6

输入样例：

输出样例：

0 0 1 2

算法思路

暴力做法直接枚举前3个数a、b、c，最后一个d可以直接算 $d = \sqrt{n - a^{2}- b^{2}-c^{2}}$ ，因为d是算出来的，可能为小数，还需判断一下 $d^{2} == n - a^{2}-b^{2}-c^{2}$ ，当条件成立是就是最后的答案。（但这道题枚举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 = sumint c;int d;public Sum(int sum, int c, int d) {this.sum = sum;this.c = c;this.d = d;}
}