#P3268. 爱吃蟠桃的孙悟空(200分)
-
1000ms
Tried: 187
Accepted: 55
Difficulty: 7
所属公司 :
华为od
爱吃蟠桃的孙悟空(200分)
思路:二分答案
和LeetCode这道题基本上一模一样,没有写过二分答案的同学可以先去写一下这道题:875. 爱吃香蕉的珂珂 - 力扣(LeetCode)\
首先,考虑一种没办法吃完所有桃树的情况,因为一次最多只能吃一棵桃树,如果桃树的总数量n比h还要大,那一定是不能满足条件的,直接输出0即可
由于,吃的速度k越大,越容易满足条件,极端情况下,k取正无穷,是一定可以满足条件的,反之k越小,则越不容易满足条件,因此是符合单调性的,可以使用二分查找求解。
二分速度k,假设当前的速度为mid,则可以遍历数组,维护一个变量cnt表示吃完所有香蕉所需要的时间,对于x根香蕉来说,所需要的时间为midx上取整,因此累加midx+mid−1即可,最终判断是否有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)
题目描述
孙悟空爱吃蟠桃,有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N 棵蟠桃树,每棵树上都桃子,守卫将在 H 小时后回来。
孙悟空可以决定他吃蟠桃的速度 K (个/每小时),每个小时选一棵桃树,并从树上吃掉 K 个,如果K大于该树上所有桃子个数,则全部吃掉,并且这一小时剩余的时间里不再吃桃。
孙悟空喜欢慢慢吃,但又想在守卫回来前吃完桃子。
请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K (K 为整数)。如果以任何速度都吃不完所有桃子,则返回 0。
输入描述
第一行输入为 N个数字, N 表示桃树的数量,这 N 个数字表示每棵桃树上蟠桃的数量。
第二行输入为一个数字,表示守卫离开的时间 H。
其中数字通过空格分割, N、 H 为正整数,每棵树上都有蟠桃,且 0<N<10000,0<H<10000。
输出描述
输出吃掉所有蟠桃的最小速度 K,无解或输入异常时输出 0。
样例1
输入
2 3 4 5
4
输出
5
样例2
输入
2 3 4 5
3
输出
0
样例3
输入
30 11 23 4 20
6
输出
23