二分答案法
解题思路
核心点：分析单调性、建立 f 函数
估计最终答案可能的范围是什么，可以定的粗略，反正二分不了几次
分析问题的答案和给定条件之间的单调性，大部分时候只需要用到自然智慧
建立一个 f 函数，当答案固定的情况下，判断给定的条件是否达标
在最终答案可能的范围上不断二分搜索，每次用 f 函数判断，直到二分结束，找到最合适的答案
⚠️ 注意
这个技巧常用且重要，一定要引起重视，非常的美、精妙！以后的课还会经常见到
爱吃香蕉的珂珂
题目链接
https://leetcode.cn/problems/koko-eating-bananas/
思路分析
首先答案范围是可以确定的，且有单调性，吃的速度越快，花的实践越少，建立 f 函数判断每个答案是否合法，在答案的范围中二分，找到本题的答案返回即可
⭐ 向上取整的写法；（a + b - 1）/ b
代码实现
java
class Solution {
// 时间复杂度 O（n * log（max）），额外空间复杂度 O（1）
public int minEatingSpeed(int[] piles, int h) {
// 定义答案范围 [l，r]
// l 最小且达标的速度
// r 最大且达标的速度
int l = 1;
int r = 0;
for (int pile : piles) {
r = Math.max(r, pile);
}
// 在答案范围内不停二分
int ans = 0;
while (l <= r) {
int mid = l + ((r - l) >> 1);
// 如果当前速度满足，尝试更小的速度
// 记答案，往左二分
if (f(piles, mid) <= h) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 香蕉重量都在 piles 中，速度定成 speed
// 返回吃完所有的香蕉，耗费的最小时数量
public long f(int[] piles, int speed) {
long ans = 0;
for (int pile : piles) {
// a / b 向上取整可以写成 (a + b - 1) / b
ans += (pile + speed - 1) / speed;
}
return ans;
}
}分割数组的最大值
题目链接
https://leetcode.cn/problems/split-array-largest-sum/
思路分析
本题是画匠问题，将一个数组划分成 k 份且连续，有很多不同的划分方法，不同的画匠分别负责相邻的划分部分且不能跨越，最后完成工作的结果取决于在这么多划分方法中，两部分累加和较大的取尽可能小的值
例如将数组 [ 6，4，5，5 ]，划分成两份，以下仅举出两个例子
第一种划分：[ 6 ]、[ 4，5，5 ]，累加和为 6，14
第二种划分：[ 6，4 ]、[ 5，5 ]，累加和为 10，10
目的是两部分累加和较大的取尽可能小的值，所以第二种划分方式是符合要求的
本题采用逆向思维，根据累加和来判定能否划分成 k 个，找到答案那个累加和
定于 f 函数，给定 limit，表示每个划分部分的累加和不超过 limit，返回需要划分成几个部分
单调性体现在当 limit 变大，即每一部分划分的累加和变多了，那需要划分的部分就变少
二分逻辑：当前给定的 limit，如果返回需要划分部分的数量小于 k，则说明每个划分部分的累加和太大了，导致了最后需要划分部分的数量变少，此时需要缩小每个划分部分的累加和，使得需要划分部分的数量增大，以达到题目要求的 k 值
反之就增大 limit，使得每个划分部分的累加和变大，缩小需要划分部分的数量
代码实现
java
class Solution {
// 时间复杂度 O（n * log（sum）），额外空间复杂度 O（1）
public int splitArray(int[] nums, int k) {
long sum = 0;
for (int num : nums) {
sum += num;
}
// 定义二分范围 [0, sum]，题目给的数据量偏大，采用 long 类型
// 从答案的角度出发，寻找符合题目要求的答案
long ans = 0;
long l = 0;
long r = sum;
while (l <= r) {
long mid = l + ((r - l) >> 1);
// 每部分累加和为 mid 的条件下，需要划分成几部分
long need = f(nums, mid);
// 此情况说明每部分的累加和太大了，才导致需要划分的部分太少
// 记答案，缩小每部分的累加和，增大需要划分的部分，往左二分
if (need <= k) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return (int) ans;
}
// 给定 limit 表示每个划分部分的累加必须 <= limit
// 返回整个数组需要划分成几个部分才能满足这个条件
public int f(int[] arr, long limit) {
int parts = 1;
int sum = 0;
for (int num : arr) {
// 返回整数最大值表示无法划分
if (num > limit) {
return Integer.MAX_VALUE;
}
if (sum + num > limit) {
parts++;
sum = num;
} else {
sum += num;
}
}
return parts;
}
}机器人跳跃问题
题目链接
https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
思路分析
题意：当前能量比下一个柱子的高度大，就加上差值，否则减去差值
初始能量越大越可能通关，因为一路都是加下去的，反而越小越吃亏，即初始能量有范围，在上面二分答案
定义 f 函数，给定一个能量和数组的最大值，判断该能量是否能通关，如果能量还有剩余，说明可以通关
⚠️ 需要注意的是如果数组全是 1，则每次都会累加 2n，增长过快以致于可能会在 long 类型的情况下溢出，加上判断，如果当前能量大于数组的最大值，结束累加，此时是可以通关的
代码实现
java
import java.io.*;
public class Main {
public static int MAXN = 100001;
public static int[] arr = new int[MAXN];
public static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
int l = 0;
int r = 0;
for (int i = 1; i <= n; i++) {
in.nextToken();
arr[i] = (int) in.nval;
r = Math.max(r, arr[i]);
}
out.println(compute(l, r, r));
}
out.flush();
out.close();
br.close();
}
// 时间复杂度 O（n * log（sum）），额外空间复杂度 O（1）
// [l，r] 范围内的初始能量，找到可以通关的初始能量
public static int compute(int l, int r, int max) {
int ans = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
// 当前的初始能量可以通关，记答案
// 尝试寻找更小的初始能量，往左二分
if (f(mid, max)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 给定初始能量值 energy，判断能否通关
public static boolean f(int energy, int max) {
// 如果数组都是 1，则每次累加 2^n ，可能会导致溢出
// 这也是传入 max 的原因，如果能量大于 max，结束累加
for (int i = 1; i <= n; i++) {
if (energy <= arr[i]) {
energy -= arr[i] - energy;
} else {
energy += energy - arr[i];
}
// 特殊判断，能量都超过了最大值，肯定通关
if (energy >= max) {
return true;
}
if (energy < 0) {
return false;
}
}
return true;
}
}找出第 K 小的数对距离
题目链接
https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
思路分析
首先差值的范围是 [ 0，最大 - 最小 ]，所以首先要对数组排序，然而第 k 小的距离必然在这个范围上
定义 f 函数，传入 limit，表示差值，返回差值为 limit 的数对有几对，在差值范围上不断二分，最终一定能找到差值为某个值，而这样的数对有 k 个
代码实现
java
class Solution {
// 时间复杂度 O（n * log（n） + log（max-min） * n），额外空间复杂度 O（1）
public int smallestDistancePair(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
int ans = 0;
// 在 [0，最大 -最小] 范围上不断二分
int l = 0;
int r = nums[n - 1] - nums[0];
while (l <= r) {
int mid = l + ((r - l) >> 1);
// 差值为 mid 的数对有几对
int cnt = f(nums, mid);
// 够 k 个，则 mid 右边的差值可定也符合条件
// 往左二分，看是否还有符合 k 的差值，继续二分
if (cnt >= k) {
ans = mid;
r = mid - 1;
} else {
// 不够 k 个，说明差值定小了，往右二分
l = mid + 1;
}
}
return ans;
}
// 给定差值 limit，返回差值 <= limit 的数字对有几对
public int f(int[] arr, int limit) {
int ans = 0;
for (int l = 0, r = 0; l < arr.length; l++) {
// 滑动窗口技巧，每次以 l 位置为基准
// 判断后面的数与 l 位置的数的差值是否 <= limit
// 如果 > limit，停止扩大窗口，计算以 l 位置为基准
// 符合条件的数对有几对，累加答案
while (r + 1 < arr.length && arr[r + 1] - arr[l] <= limit) {
r++;
}
// 例如数组 arr[0...3]，差值对数如下
// （0，1）位置一对、（0，2）位置一对，（0，3）位置一对
// 1 开头的哪些等 l++ 之后才计算
ans += r - l;
}
return ans;
}
}同时运行 N 台电脑的最长时间
题目链接
https://leetcode.cn/problems/maximum-running-time-of-n-computers/
思路分析
定义碎片电池：电池的电量小于要求的运行时间
⭐ 结论：如果全是碎片电池，碎片电池的电量总和 >= 要求的运行时间 * 电脑台数，则一定可以达成要求的运行时间
对于电池电量 > 要求的运行时间的电池，可以先不考虑，排除了这些不考虑的电池后，如果剩余的电池都能达成条件，那这些电池就能达成电脑要求的运行时间
单调性的体现：让 n 台电脑运行 x 分钟更易，运行 x + 1 分钟更难
定义 f 函数，只考虑碎片电池的总电量能否使得电脑运行 x 分钟
二分的逻辑：如果这些电池的总电量足以实现要求运行 x 分钟，那么看看运行 x + 1 分钟及更多分钟能否达成，不断调整二分的区间，用答案来验证是否满足条件，满足条件的一定是答案
代码实现
java
class Solution {
// 原来这里是 int n, int[] batteries
// 这里改成 int num, int[] arr
// 时间复杂度 O（n * log（sum）），额外空间复杂度 O（1）
public long maxRunTime(int num, int[] arr) {
long sum = 0;
for (int x : arr) {
sum += x;
}
long ans = 0;
// 在 [0，sum] 范围上二分
long l = 0;
long r = sum;
while (l <= r) {
long mid = l + ((r - l) >> 1);
// 如果电量足以让 num 台电脑运行 mid 的时间
// 往右二分，看看 mid + 1及更多的时间能否运行
if (f(arr, num, mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
// 只关注碎片电池，不考虑电池电量 > 要求运行时间的电池
// 碎片电池的总电量能否使得 num 台电脑运行 time 的时间
public boolean f(int[] arr, int num, long time) {
// 碎片电池电量总和
long sum = 0;
for (int x : arr) {
if (x > time) {
num--;
} else {
// x <= time，是碎片电池
sum += x;
}
// 核心结论的运用
if (sum >= (long) num * time) {
return true;
}
}
return false;
}
}优化实现
贪心优化，找到最大的电池电量 max，如果 sum > max * num，对于 num 台电脑，每台电脑需要供电 max 分钟，需要的总电量都 < sum，则说明供电时间一定 >= max
既然 max <= 需要的供电时间，那说明所有电池都是碎片电池，那供电时间不就是 sum / num
此时二分范围从 [ 0，sum ] 优化到了 [ 0，max ]，二分跑的更快
java
class Solution {
// 原来这里是 int n, int[] batteries
// 这里改成 int num, int[] arr
// 时间复杂度 O（n * log（sum）），额外空间复杂度 O（1）
public long maxRunTime(int num, int[] arr) {
int max = 0;
long sum = 0;
for (int x : arr) {
max = Math.max(max, x);
sum += x;
}
// 贪心优化
if (sum > (long) max * num) {
// 所有电池的最大电量是max
// 如果此时sum > (long) max * num，
// 说明 : 最终的供电时间一定在 >= max，而如果最终的供电时间 >= max
// 说明 : 对于最终的答案X来说，所有电池都是课上讲的"碎片拼接"的概念
// 那么寻找 ? * num <= sum 的情况中，尽量大的 ? 即可
// 即sum / num
return sum / num;
}
// 此时二分范围从 [0，sum] 优化到了 [0，max]，跑的更快
int ans = 0;
int l = 0;
int r = max;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (f(arr, num, mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
public boolean f(int[] arr, int num, int time) {
// 碎片电池电量总和
long sum = 0;
for (int x : arr) {
if (x > time) {
num--;
} else {
sum += x;
}
if (sum >= (long) num * time) {
return true;
}
}
return false;
}
}计算等位时间
题目描述
给定一个数组 arr 长度为 n，表示 n 个服务员，每服务一个人的时间
给定一个正数 m，表示有 m 个人等位，如果你是刚来的人，每个客人都遵循有空位就上的原则，请问你需要等多久？
假设 m 远远大于 n，比如 n <= 103，m <= 109，该怎么做是最优解？
谷歌的面试，这个题连考了 2 个月
思路分析
假设所有服务员都服务 x 的时间，看能否服务 m + 1 个人（自己是第 m + 1 位），等到自己，可能没开始服务，但是要求能够服务到自己
设定服务的时间范围：[ 0， min * n ]，假设所有人都选择服务时间较短的服务员，则自己至少要等 min * n 的时间，这个范围可以很粗，也二分不了几次
在给定的时间范围上二分，找到可以满足服务 m + 1 个人的时间
代码实现
java
class Solution {
public int waitingTime(int[] arr, int w) {
int min = Integer.MAX_VALUE;
for (int x : arr) {
min = Math.min(min, x);
}
int ans = 0;
int l = 0;
// 至少等这么久才轮到自己
int r = min * w;
while (l <= r) {
int mid = l + ((r - l) >> 1);
// 当前时间足以服务 w + 1 个人
// 往左二分，寻找更短的等待时间
if (f(arr, mid) >= w + 1) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 如果每个服务员都服务 time 的时间，可以接待
// 几位客人（结束的，开始的客人都要算）
public int f(int[] arr, int time) {
int ans = 0;
for (int num : arr) {
// 要算上自己，所以 +1
ans += (time / num) + 1;
}
return ans;
}
}对数器验证
java
package class051;
import java.util.PriorityQueue;
// 计算等位时间
// 给定一个数组arr长度为n，表示n个服务员，每服务一个人的时间
// 给定一个正数m，表示有m个人等位，如果你是刚来的人，请问你需要等多久？
// 假设m远远大于n，比如n <= 10^3, m <= 10^9，该怎么做是最优解？
// 谷歌的面试，这个题连考了2个月
// 找不到测试链接，所以用对数器验证
public class Code06_WaitingTime {
// 堆模拟
// 验证方法，不是重点
// 如果m很大，该方法会超时
// 时间复杂度O(m * log(n))，额外空间复杂度O(n)
public static int waitingTime1(int[] arr, int m) {
// 一个一个对象int[]
// [醒来时间，服务一个客人要多久]
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
int n = arr.length;
for (int i = 0; i < n; i++) {
heap.add(new int[] { 0, arr[i] });
}
for (int i = 0; i < m; i++) {
int[] cur = heap.poll();
cur[0] += cur[1];
heap.add(cur);
}
return heap.peek()[0];
}
// 二分答案法
// 最优解
// 时间复杂度O(n * log(min * w))，额外空间复杂度O(1)
public static int waitingTime2(int[] arr, int w) {
int min = Integer.MAX_VALUE;
for (int x : arr) {
min = Math.min(min, x);
}
int ans = 0;
for (int l = 0, r = min * w, m; l <= r;) {
// m中点，表示一定要让服务员工作的时间！
m = l + ((r - l) >> 1);
// 能够给几个客人提供服务
if (f(arr, m) >= w + 1) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
// 如果每个服务员工作time，可以接待几位客人（结束的、开始的客人都算）
public static int f(int[] arr, int time) {
int ans = 0;
for (int num : arr) {
ans += (time / num) + 1;
}
return ans;
}
// 对数器测试
public static void main(String[] args) {
System.out.println("测试开始");
int N = 50;
int V = 30;
int M = 3000;
int testTime = 20000;
for (int i = 0; i < testTime; i++) {
int n = (int) (Math.random() * N) + 1;
int[] arr = randomArray(n, V);
int m = (int) (Math.random() * M);
int ans1 = waitingTime1(arr, m);
int ans2 = waitingTime2(arr, m);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
// 对数器测试
public static int[] randomArray(int n, int v) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * v) + 1;
}
return arr;
}
}测试链接
https://leetcode.cn/problems/minimum-time-to-complete-trips/
本题要求的是需要完成 w 趟旅行，没有到自己的概念，所以不需要 +1 处理
在数据上有些变化，需要改成 long 类型，除此以外与再无区别
java
class Solution {
// 原来是 int[] time, int totalTrips
// 这里改成 int[] arr, int w
public long minimumTime(int[] arr, int w) {
int min = Integer.MAX_VALUE;
for (int x : arr) {
min = Math.min(min, x);
}
long ans = 0;
long l = 0;
// 至少等这么久才轮到自己
long r = (long)min * w;
while (l <= r) {
long mid = l + ((r - l) >> 1);
// 要求完成多少趟旅行，不需要 +1
// 往左二分，寻找更短的时间花费
if (f(arr, mid) >= w) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// 如果每个服务员都服务 time 的时间，可以接待
// 几位客人（结束的，开始的客人都要算）
public long f(int[] arr, long time) {
long ans = 0;
for (int num : arr) {
// 要求完成多少趟旅行，不需要 +1
ans += (time / num);
}
return ans;
}
}刀砍毒杀怪兽问题
题目描述
怪兽的初始血量是一个整数 hp，给出每一回合刀砍和毒杀的数值 cuts 和 poisons
第 i 回合如果用刀砍，怪兽在这回合会直接损失 cuts [ i ] 的血，不再有后续效果
第 i 回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失 poisons [ i ] 的血量
并且你选择的所有毒杀效果，在之后的回合都会叠加
两个数组 cuts、poisons，长度都是 n，代表你一共可以进行 n 回合
每一回合你只能选择刀砍或者毒杀中的一个动作
如果你在 n 个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
但是怪兽如果有中毒效果的话，那么怪兽依然会在血量耗尽的那回合死掉
返回至少多少回合，怪兽会死掉
数据范围如下
1 <= n <= 105
1 <= hp <= 109
1 <= cuts [ i ]、poisons [ i ] <= 109
本题来自真实大厂笔试，找不到测试链接，所以用对数器验证
思路分析
正着求不好求，对于每一回合选择刀砍还是毒杀不好抉择
单调性的体现：回合数越多，怪兽死的可能性越大
逆向思维二分答案，要求 n 回合怪兽必须死，那对于抉择刀砍还是毒杀就很好选了
例如当前是第 10 回合， 要求第 12 回合怪兽必须死，当然是选择刀砍，因为只有 2 回合的机会，要使怪兽扣的血量尽可能的多
代码实现
java
class Solution {
// 时间复杂度：O（n * log（hp）），额外空间复杂度：O（1）
public int fast(int[] cuts, int[] poison, int hp) {
int ans = Integer.MAX_VALUE;
int l = 1;
int r = hp + 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
// 如果 mid 回合能让怪兽死，那更多的回合肯定可以
// 记答案，往左二分，看更少的回合能否将怪兽杀死
if (f(cuts, poison, hp, mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
}
// cuts ：刀砍伤害，poisons ：毒啥伤害
// hp ：怪兽血量，limit ：回合限制
// 给定 limit 回合限制，返回能不能将怪兽杀死
public boolean f(int[] cuts, int[] poisons, long hp, int limit) {
// 取有效的回合数
int n = Math.min(cuts.length, limit);
for (int i = 0, j = 1; i < n; i++, j++) {
// 如果采用毒杀伤害，本轮不会生效，limit - j 才是生效的回合
// 在之后的每一轮都会生效，伤害需要累加，所以采用相乘关系
hp -= Math.max((long) cuts[i], (long) (limit - j) * (long) poisons[i]);
if (hp <= 0) {
return true;
}
}
return false;
}
}对数器验证
java
package class051;
// 刀砍毒杀怪兽问题
// 怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
// 第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
// 第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
// 并且你选择的所有毒杀效果，在之后的回合都会叠加
// 两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
// 每一回合你只能选择刀砍或者毒杀中的一个动作
// 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
// 但是怪兽如果有中毒效果的话，那么怪兽依然会在血量耗尽的那回合死掉
// 返回至少多少回合，怪兽会死掉
// 数据范围 :
// 1 <= n <= 10^5
// 1 <= hp <= 10^9
// 1 <= cuts[i]、poisons[i] <= 10^9
// 本题来自真实大厂笔试，找不到测试链接，所以用对数器验证
public class Code07_CutOrPoison {
// 动态规划方法(只是为了验证)
// 目前没有讲动态规划，所以不需要理解这个函数
// 这个函数只是为了验证二分答案的方法是否正确的
// 纯粹为了写对数器验证才设计的方法，血量比较大的时候会超时
// 这个方法不做要求，此时并不需要理解，可以在学习完动态规划章节之后来看看这个函数
public static int fast1(int[] cuts, int[] poisons, int hp) {
int sum = 0;
for (int num : poisons) {
sum += num;
}
int[][][] dp = new int[cuts.length][hp + 1][sum + 1];
return f1(cuts, poisons, 0, hp, 0, dp);
}
// 不做要求
public static int f1(int[] cuts, int[] poisons, int i, int r, int p, int[][][] dp) {
r -= p;
if (r <= 0) {
return i + 1;
}
if (i == cuts.length) {
if (p == 0) {
return Integer.MAX_VALUE;
} else {
return cuts.length + 1 + (r + p - 1) / p;
}
}
if (dp[i][r][p] != 0) {
return dp[i][r][p];
}
int p1 = r <= cuts[i] ? (i + 1) : f1(cuts, poisons, i + 1, r - cuts[i], p, dp);
int p2 = f1(cuts, poisons, i + 1, r, p + poisons[i], dp);
int ans = Math.min(p1, p2);
dp[i][r][p] = ans;
return ans;
}
// 二分答案法
// 最优解
// 时间复杂度O(n * log(hp))，额外空间复杂度O(1)
public static int fast2(int[] cuts, int[] poisons, int hp) {
int ans = Integer.MAX_VALUE;
for (int l = 1, r = hp + 1, m; l <= r;) {
// m中点，一定要让怪兽在m回合内死掉，更多回合无意义
m = l + ((r - l) >> 1);
if (f(cuts, poisons, hp, m)) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
// cuts、posions，每一回合刀砍、毒杀的效果
// hp：怪兽血量
// limit：回合的限制
public static boolean f(int[] cuts, int[] posions, long hp, int limit) {
int n = Math.min(cuts.length, limit);
for (int i = 0, j = 1; i < n; i++, j++) {
hp -= Math.max((long) cuts[i], (long) (limit - j) * (long) posions[i]);
if (hp <= 0) {
return true;
}
}
return false;
}
// 对数器测试
public static void main(String[] args) {
// 随机测试的数据量不大
// 因为数据量大了，fast1方法会超时
// 所以在数据量不大的情况下，验证fast2方法功能正确即可
// fast2方法在大数据量的情况下一定也能通过
// 因为时间复杂度就是最优的
System.out.println("测试开始");
int N = 30;
int V = 20;
int H = 300;
int testTimes = 10000;
for (int i = 0; i < testTimes; i++) {
int n = (int) (Math.random() * N) + 1;
int[] cuts = randomArray(n, V);
int[] posions = randomArray(n, V);
int hp = (int) (Math.random() * H) + 1;
int ans1 = fast1(cuts, posions, hp);
int ans2 = fast2(cuts, posions, hp);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
// 对数器测试
public static int[] randomArray(int n, int v) {
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = (int) (Math.random() * v) + 1;
}
return ans;
}
}