阅读量:0
本题已有网友报告代码100%通过率
本题视频讲解：视频讲解
OJ &答疑服务
购买任意专栏，即可私信博主，获取答疑/辅导服务
OJ权限获取可以在购买专栏后访问网站：首页 - CodeFun2000
题目描述
孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N N N棵蟠桃树，每颗树上都桃子，守卫将在 H H H 小时后回来。
孙悟空可以决定他吃蟠桃的速度 K K K （个/每小时），每个小时选一棵桃树，并从树上吃掉 K K K 个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。
孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。
请返回孙悟空可以在 H H H 小时内吃掉所有桃子的最小速度 K K K （ K K K 为整数）。如果以任何速度都吃不完所有桃子，则返回 0 0 0。
输入描述
第一行输入为 N N N个数字， N N N 表示桃树的数量，这 N N N 个数字表示每棵桃树上蟠桃的数量。
第二行输入为一个数字，表示守卫离开的时间 H H H。
其中数字通过空格分割， N N N、 H H H 为正整数，每棵树上都有蟠桃，且 $0 < N < 10000 ,0 < H < 10000 $。
输出描述
输出吃掉所有蟠桃的最小速度 K K K，无解或输入异常时输出 0 0 0。
样例1
输入
2 3 4 5 4 输出
5 样例2
输入
2 3 4 5 3 输出
0 样例3
输入
30 11 23 4 20 6 输出
23 思路：二分答案
和LeetCode这道题基本上一模一样，没有写过二分答案的同学可以先去写一下这道题：875. 爱吃香蕉的珂珂 - 力扣（LeetCode）\
首先，考虑一种没办法吃完所有桃树的情况，因为一次最多只能吃一棵桃树，如果桃树的总数量 n n n比 h h h还要大，那一定是不能满足条件的，直接输出0即可
由于，吃的速度 k k k越大，越容易满足条件，极端情况下， k k k取正无穷，是一定可以满足条件的，反之 k k k越小，则越不容易满足条件，因此是符合单调性的，可以使用二分查找求解。
二分速度 k k k，假设当前的速度为 m i d mid mid,则可以遍历数组，维护一个变量 c n t cnt cnt表示吃完所有香蕉所需要的时间，对于 x x x根香蕉来说，所需要的时间为 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 ≤ h cnt\le h cnt≤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<bits/stdc++.h> // 引入所有标准库头文件 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"); // 如果桃树数量大于规定时间，输出0 else{ 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 False return True l,r=1,10**9 #二分左右边界 while l<r: mid=l+r>>1 if check(mid): r=mid else: l=mid+1 print(l) 