class051 二分答案法与相关题目【算法】

class051 二分答案法与相关题目【算法】

算法讲解051【必备】二分答案法与相关题目
在这里插入图片描述

code1 875. 爱吃香蕉的珂珂

// 爱吃香蕉的珂珂
// 珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉
// 警卫已经离开了,将在 h 小时后回来。
// 珂珂可以决定她吃香蕉的速度 k (单位:根/小时)
// 每个小时,她将会选择一堆香蕉,从中吃掉 k 根
// 如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉
// 珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
// 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)
// 测试链接 : https://leetcode.cn/problems/koko-eating-bananas/

package class051;

// 爱吃香蕉的珂珂
// 珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉
// 警卫已经离开了,将在 h 小时后回来。
// 珂珂可以决定她吃香蕉的速度 k (单位:根/小时)
// 每个小时,她将会选择一堆香蕉,从中吃掉 k 根
// 如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉
// 珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
// 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)
// 测试链接 : https://leetcode.cn/problems/koko-eating-bananas/
public class Code01_KokoEatingBananas {

	// 时间复杂度O(n * log(max)),额外空间复杂度O(1)
	public static int minEatingSpeed(int[] piles, int h) {
		// 最小且达标的速度,范围[l,r]
		int l = 1;
		int r = 0;
		for (int pile : piles) {
			r = Math.max(r, pile);
		}
		// [l,r]不停二分
		int ans = 0;
		int m = 0;
		while (l <= r) {
			// m = (l + r) / 2
			m = l + ((r - l) >> 1);
			if (f(piles, m) <= h) {
				// 达标!
				// 记录答案,去左侧二分
				ans = m;
				// l....m....r
				// l..m-1
				r = m - 1;
			} else {
				// 不达标
				l = m + 1;
			}
		}
		return ans;
	}

	// 香蕉重量都在piles
	// 速度就定成speed
	// 返回吃完所有的香蕉,耗费的小时数量
	public static long f(int[] piles, int speed) {
		long ans = 0;
		for (int pile : piles) {
			// (a/b)结果向上取整,如果a和b都是非负数,可以写成(a+b-1)/b
			// "讲解032-位图"讲了这种写法,不会的同学可以去看看
			// 这里不再赘述
			ans += (pile + speed - 1) / speed;
		}
		return ans;
	}

}

code2 410. 分割数组的最大值

// 分割数组的最大值(画匠问题)
// 给定一个非负整数数组 nums 和一个整数 m
// 你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
// 测试链接 : https://leetcode.cn/problems/split-array-largest-sum/

package class051;

// 分割数组的最大值(画匠问题)
// 给定一个非负整数数组 nums 和一个整数 m
// 你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
// 测试链接 : https://leetcode.cn/problems/split-array-largest-sum/
public class Code02_SplitArrayLargestSum {

	// 时间复杂度O(n * log(sum)),额外空间复杂度O(1)
	public static int splitArray(int[] nums, int k) {
		long sum = 0;
		for (int num : nums) {
			sum += num;
		}
		long ans = 0;
		// [0,sum]二分
		for (long l = 0, r = sum, m, need; l <= r;) {
			// 中点m
			m = l + ((r - l) >> 1);
			// 必须让数组每一部分的累加和 <= m,请问划分成几个部分才够!
			need = f(nums, m);
			if (need <= k) {
				// 达标
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return (int) ans;
	}

	// 必须让数组arr每一部分的累加和 <= limit,请问划分成几个部分才够!
	// 返回需要的部分数量
	public static 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;
	}

}

code3 机器人跳跃问题

// 机器人跳跃问题
// 机器人正在玩一个古老的基于DOS的游戏
// 游戏中有N+1座建筑,从0到N编号,从左到右排列
// 编号为0的建筑高度为0个单位,编号为i的建筑的高度为H(i)个单位
// 起初机器人在编号为0的建筑处
// 每一步,它跳到下一个(右边)建筑。假设机器人在第k个建筑,且它现在的能量值是E
// 下一步它将跳到第个k+1建筑
// 它将会得到或者失去正比于与H(k+1)与E之差的能量
// 如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值
// 游戏目标是到达第个N建筑,在这个过程中,能量值不能为负数个单位
// 现在的问题是机器人以多少能量值开始游戏,才可以保证成功完成游戏
// 测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

package class051;

// 机器人跳跃问题
// 机器人正在玩一个古老的基于DOS的游戏
// 游戏中有N+1座建筑,从0到N编号,从左到右排列
// 编号为0的建筑高度为0个单位,编号为i的建筑的高度为H(i)个单位
// 起初机器人在编号为0的建筑处
// 每一步,它跳到下一个(右边)建筑。假设机器人在第k个建筑,且它现在的能量值是E
// 下一步它将跳到第个k+1建筑
// 它将会得到或者失去正比于与H(k+1)与E之差的能量
// 如果 H(k+1) > E 那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值
// 游戏目标是到达第个N建筑,在这个过程中,能量值不能为负数个单位
// 现在的问题是机器人以多少能量值开始游戏,才可以保证成功完成游戏
// 测试链接 : https://www.nowcoder.com/practice/7037a3d57bbd4336856b8e16a9cafd71
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code03_RobotPassThroughBuilding {

	public static int MAXN = 100001;

	public static int[] arr = new int[MAXN];

	public static int n;

	public static void main(String[] args) throws IOException {
		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();
	}

	// [l,r]通关所需最小能量的范围,不停二分
	// max是所有建筑的最大高度
	// 时间复杂度O(n * log(max)),额外空间复杂度O(1)
	public static int compute(int l, int r, int max) {
		int m, ans = -1;
		while (l <= r) {
			// m中点,此时通关所需规定的初始能量
			m = l + ((r - l) >> 1);
			if (f(m, max)) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	// 初始能量为energy,max是建筑的最大高度,返回能不能通关
	// 为什么要给定建筑的最大高度?
	public static boolean f(int energy, int max) {
		// 注意!
		// 如果给的能量值很大,那么后续能量增长将非常恐怖
		// 完全有可能超出long的范围
		// 所以要在遍历时,一定要加入energy >= 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;
	}

}

code4 719. 找出第 K 小的数对距离

// 找出第K小的数对距离
// 数对 (a,b) 由整数 a 和 b 组成,其数对距离定义为 a 和 b 的绝对差值。
// 给你一个整数数组 nums 和一个整数 k
// 数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
// 返回 所有数对距离中 第 k 小的数对距离。
// 测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/

package class051;

import java.util.Arrays;

// 找出第K小的数对距离
// 数对 (a,b) 由整数 a 和 b 组成,其数对距离定义为 a 和 b 的绝对差值。
// 给你一个整数数组 nums 和一个整数 k
// 数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length
// 返回 所有数对距离中 第 k 小的数对距离。
// 测试链接 : https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
public class Code04_FindKthSmallestPairDistance {

	// 时间复杂度O(n * log(n) + log(max-min) * n),额外空间复杂度O(1)
	public static int smallestDistancePair(int[] nums, int k) {
		int n = nums.length;
		Arrays.sort(nums);
		int ans = 0;
		// [0, 最大-最小],不停二分
		for (int l = 0, r = nums[n - 1] - nums[0], m, cnt; l <= r;) {
			// m中点,arr中任意两数的差值 <= m
			m = l + ((r - l) >> 1);
			// 返回数字对的数量
			cnt = f(nums, m);
			if (cnt >= k) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	// arr中任意两数的差值 <= limit
	// 这样的数字配对,有几对?
	public static int f(int[] arr, int limit) {
		int ans = 0;
		// O(n)
		for (int l = 0, r = 0; l < arr.length; l++) {
			// l......r r+1
			while (r + 1 < arr.length && arr[r + 1] - arr[l] <= limit) {
				r++;
			}
			// arr[l...r]范围上的数差值的绝对值都不超过limit
			// arr[0...3]
			// 0,1
			// 0,2
			// 0,3
			ans += r - l;
		}
		return ans;
	}

}

code5 2141. 同时运行 N 台电脑的最长时间

// 同时运行N台电脑的最长时间
// 你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
// 其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
// 你想使用这些电池让 全部 n 台电脑 同时 运行。
// 一开始,你可以给每台电脑连接 至多一个电池
// 然后在任意整数时刻,你都可以将一台电脑与它的电池断开连接,并连接另一个电池,你可以进行这个操作 任意次
// 新连接的电池可以是一个全新的电池,也可以是别的电脑用过的电池
// 断开连接和连接新的电池不会花费任何时间。
// 注意,你不能给电池充电。
// 请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
// 测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/

package class051;

// 同时运行N台电脑的最长时间
// 你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
// 其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
// 你想使用这些电池让 全部 n 台电脑 同时 运行。
// 一开始,你可以给每台电脑连接 至多一个电池
// 然后在任意整数时刻,你都可以将一台电脑与它的电池断开连接,并连接另一个电池,你可以进行这个操作 任意次
// 新连接的电池可以是一个全新的电池,也可以是别的电脑用过的电池
// 断开连接和连接新的电池不会花费任何时间。
// 注意,你不能给电池充电。
// 请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
// 测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/
public class Code05_MaximumRunningTimeOfNComputers {

	// 单纯的二分答案法
	// 提交时把函数名改为maxRunTime
	// 时间复杂度O(n * log(sum)),额外空间复杂度O(1)
	public static long maxRunTime1(int num, int[] arr) {
		long sum = 0;
		for (int x : arr) {
			sum += x;
		}
		long ans = 0;
		// [0, sum],不停二分
		for (long l = 0, r = sum, m; l <= r;) {
			// m中点,让num台电脑共同运行m分钟,能不能做到
			m = l + ((r - l) >> 1);
			if (f1(arr, num, m)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans;
	}

	// 让num台电脑共同运行time分钟,能不能做到
	public static boolean f1(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;
	}

	// 二分答案法 + 增加分析(贪心)
	// 提交时把函数名改为maxRunTime
	// 时间复杂度O(n * log(max)),额外空间复杂度O(1)
	public static long maxRunTime2(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;
		}
		// 最终的供电时间一定在 < max范围上
		// [0, sum]二分范围,可能定的比较粗,虽然不影响,但毕竟是有点慢
		// [0, max]二分范围!更精细的范围,二分次数会变少
		int ans = 0;
		for (int l = 0, r = max, m; l <= r;) {
			m = l + ((r - l) >> 1);
			if (f2(arr, num, m)) {
				ans = m;
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return ans;
	}

	public static boolean f2(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;
	}

}

code6 计算等位时间

// 计算等位时间
// 给定一个数组arr长度为n,表示n个服务员,每服务一个人的时间
// 给定一个正数m,表示有m个人等位,如果你是刚来的人,请问你需要等多久?
// 假设m远远大于n,比如n <= 10^3, m <= 10^9,该怎么做是最优解?
// 谷歌的面试,这个题连考了2个月
// 找不到测试链接,所以用对数器验证

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;
	}

}

code7 刀砍毒杀怪兽问题

// 刀砍毒杀怪兽问题
// 怪兽的初始血量是一个整数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
// 本题来自真实大厂笔试,找不到测试链接,所以用对数器验证

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;
	}

}

滴滴20230908 糖果工厂

糖果工厂可以生产n种不同的糖果,假设这些糖果的编号分别为1到n,每一天工厂可以生产ci个编号为i的糖果。
今天工厂接到了一个订单,需求是a包糖果,且每包糖果必须是同一种类的,每包数量不能少于b个。假设糖果工厂在无存货的情况下,至少需要多少天才能完成这个订单?

输入描述
第一行是三个正整数n、a、b,分别表示糖果工厂可以生成的糖果种类数,订单的需求是a包糖果,每包不少于b个。
第二行是n个正整数c1c2…cn,其中第i个数ci表示工厂每天能生产的编号为i的糖果的数量。对所有的数据证:1<=n<=100000,1<=a,b<=10^7,1<=ci<=10000

输出描述
一行一个正整数,表示完成订单所需的最少天数

输入
3 10 20
7 9 6

输出
10

/*
工厂可以生产n种糖果,糖果编号为1到n,工厂每天生产i号糖果的数量为arr【i】,不同编号的糖果并行生产。
工厂接到一个订单,要求是a包糖果、每包糖果必须是同一种类、每包的数量不能少于b个。
一种糖果可以生产很多包。返回至少需要多少天才能完成订单。

解法:根据天数二分。假设生产x天,那么每号糖果都可以算出生产x天能凑几包,然后看看所有糖果能不能凑够a包。
凑不够在x右侧二分;凑够让ans=x,去x左侧二分。学起来吧!二分答案法真的重要!

输入
3 10 20
7 9 6
输出
10
 */
public class Main {
    public static void main(String[] args) {
        int n=3;
        int a=10;
        int b=20;
        int[] arr=new int[]{7,9,6};

        int max=0;
        for (int i = 0; i < n; i++) {
            max=Math.max(max,arr[i]);
        }

        int l=1;
        int r=a*b/max;
        int res=0;
        while (l<=r){
            int m=(l+r)/2;
            int cur=f(arr,b,m);
            if(cur>=a){
                res=m;
                r=m-1;
            }else {
                l=m+1;
            }
        }

        System.out.println(res);

    }

    //生产x天,每包b个,能够有多少包糖果
    public static int f(int[] arr,int b,int x){
        int res=0;
        for (int n:arr){
            res+=n*x/b;
        }
        return res;
    }


}

2023-12-6 19:06:27

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>