本题已有网友报告代码100%通过率
本题视频讲解:视频讲解
OJ &答疑服务
购买任意专栏,即可添加博主vx:utheyi,获取答疑/辅导服务
OJ权限获取可以在购买专栏后访问网站:首页 – CodeFun2000
题目描述
孙悟空爱吃蟠桃,有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 NNN棵蟠桃树,每颗树上都桃子,守卫将在 HHH 小时后回来。
孙悟空可以决定他吃蟠桃的速度 KKK (个/每小时),每个小时选一棵桃树,并从树上吃掉 KKK 个,则全部吃掉,并且这一小时剩余的时间里不再吃桃。
孙悟空喜欢慢慢吃,但又想在守卫回来前吃完桃子。
请返回孙悟空可以在 HHH 小时内吃掉所有桃子的最小速度 KKK ( KKK 为整数)。如果以任何速度都吃不完所有桃子,则返回 000。
输入描述
第一行输入为 NNN个数字, NNN 表示桃树的数量,这 NNN 个数字表示每棵桃树上蟠桃的数量。
第二行输入为一个数字,表示守卫离开的时间 HHH。
其中数字通过空格分割, NNN、 HHH 为正整数,每棵树上都有蟠桃,且 $0 < N < 10000 ,0 < H < 10000 $。
输出描述
输出吃掉所有蟠桃的最小速度 KKK,无解或输入异常时输出 000。
样例1
输入
2 3 4 54
输出
5
样例2
输入
2 3 4 53
输出
0
样例3
输入
30 11 23 4 206
输出
23
思路:二分答案
和LeetCode这道题基本上一模一样,没有写过二分答案的同学可以先去写一下这道题:875. 爱吃香蕉的珂珂 – 力扣(LeetCode)\
首先,考虑一种没办法吃完所有桃树的情况,因为一次最多只能吃一棵桃树,如果桃树的总数量 nnn比 hhh还要大,那一定是不能满足条件的,直接输出0
即可
由于,吃的速度 kkk越大,越容易满足条件,极端情况下, kkk取正无穷,是一定可以满足条件的,反之 kkk越小,则越不容易满足条件,因此是符合单调性的,可以使用二分查找求解。
二分速度 kkk,假设当前的速度为 m i dmidmid,则可以遍历数组,维护一个变量 c n tcntcnt表示吃完所有香蕉所需要的时间,对于 xxx根香蕉来说,所需要的时间为 x m i d \frac{x}{mid}midx上取整,因此累加x + m i d − 1 m i d \frac{x+mid-1}{mid}midx+mid−1即可,最终判断是否有 c n t ≤ hcnt\le hcnt≤h。
JavaScript代码
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout});let w = [];let h = 0;rl.on('line', (line) => {if (w.length === 0) {w = line.split(' ').map(Number);// 读入n个数字} else if (h === 0) {h = parseInt(line);let n = w.length;if (n > h) {// 每小时最多只能吃一颗桃树,因此没办法吃完所有桃树console.log(0);} else {let l = 1, r = 1e9;// 二分左右边界while (l < r) {let mid = Math.floor((l + r) / 2);if (check(w, h, mid)) {r = mid;} else {l = mid + 1;}}console.log(l);}}});function check(w, h, x) {let cnt = 0;// 记录吃完所有桃树的时间for (let num of w) {cnt += Math.floor((num + x - 1) / x);// 吃掉数量为num的一颗桃树所需要的时间if (cnt > h) {return false;}}return true;}
Java代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] input = sc.nextLine().split(" ");// 读入n个数字int h = Integer.parseInt(sc.nextLine());int n = input.length;int[] w = new int[n];for (int i = 0; i < n; i++) {w[i] = Integer.parseInt(input[i]);}if (n > h) {// 每小时最多只能吃一颗桃树,因此没办法吃完所有桃树System.out.println(0);} else {int l = 1, r = (int) 1e9;// 二分左右边界while (l < r) {int mid = l + (r - l) / 2;if (check(w, h, mid)) {r = mid;} else {l = mid + 1;}}System.out.println(l);}}static boolean check(int[] w, int h, int x) {int cnt = 0;// 记录吃完所有桃树的时间for (int num : w) {cnt += (num + x - 1) / x;// 吃掉数量为num的一颗桃树所需要的时间if (cnt > h) {return false;}}return true;}}
C++代码
#include// 引入所有标准库头文件using namespace std;const int N=1E5+10;// 定义数组大小int w[N],h,n;// 定义桃树数量、小时数和桃树数组bool check(int x){// 判断当吃的速度为x的时候,是否能吃完所有桃树int cnt=0;// 记录吃完所有桃树的时间for(int i=1;i<=n;i++){cnt+=(w[i]+x-1)/x;// 吃掉数量为w[i]的一颗桃树所需要的时间if(cnt>h)return false;// 如果吃完所有桃树的时间超过了规定时间,返回false}return true;// 如果吃完所有桃树的时间不超过规定时间,返回true}int main(){while(cin>>w[++n]);// 读入桃树数量和每颗桃树的数量h=w[--n];// 最后一个数为规定时间,将其赋值给h--n;// 桃树数量减一if(n>h)puts("0");// 如果桃树数量大于规定时间,输出0else{int l=1,r=1e9;// 二分左右边界while(l<r){int mid=l+r>>1;// 取中间值if(check(mid))r=mid;// 如果能吃完所有桃树,将右边界移动到中间值else l=mid+1;// 如果不能吃完所有桃树,将左边界移动到中间值+1}cout<<l<<endl;// 输出最小速度}return 0;}
Python代码
w=list(map(int,input().split()))#读入n个数字h=int(input())n=len(w)if n>h:#每小时最多只能吃一颗桃树,因此没办法吃完所有桃树print(0)else:def check(x):#判断当吃的速度为x的时候,是否能吃完所有桃树cnt=0#记录吃完所有桃树的时间for num in w:cnt+=(num+x-1)//x#吃掉数量为num的一颗桃树所需要的时间if cnt>h:return Falsereturn Truel,r=1,10**9#二分左右边界while l<r:mid=l+r>>1if check(mid):r=midelse:l=mid+1print(l)