小招喵喜欢吃喵粮。这里有 N 堆喵粮，第 i 堆中有 p[i] 粒喵粮。喵主人离开了，将在 H 小时后回来。
小招喵可以决定她吃喵粮的速度 K （单位：粒/小时）。每个小时，她将会选择一堆喵粮，从中吃掉 K 粒。如果这堆喵粮少于 K 粒，她将吃掉这堆的所有喵粮，然后这一小时内不会再吃更多的喵粮。
小招喵喜欢慢慢吃，但仍然想在喵主人回来前吃掉所有的喵粮。
返回她可以在 H 小时内吃掉所有喵粮的最小速度 K（K 为整数）。
[编程题]爱吃喵粮的小招喵
在[1,max(p)]上使用二分法求符合要求的速度，能把时间控制在H小时之内就降速尝试，否则加速尝试。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strs = br.readLine().split(" ");
int n = strs.length;
int[] foods = new int[n];
// 速度下线为1，上线为max(foods)
int lb = 1, ub = 0;
for(int i = 0; i < n; i++){
foods[i] = Integer.parseInt(strs[i]);
ub = ub < foods[i]? foods[i]: ub;
}
int H = Integer.parseInt(br.readLine());
int v = ub;
while(lb <= ub){
int m = lb + ((ub - lb) >> 1);
if(timeConsume(foods, m) <= H){
// 速度足够，往左二分
v = m;
ub = m - 1;
}else{
// 速度不够，往右二分
lb = m + 1;
}
}
System.out.println(v);
}
private static int timeConsume(int[] foods, int v) {
int time = 0;
for(int i = 0; i < foods.length; i++){
time += (foods[i] + v - 1) / v;
}
return time;
}
}
发表于 2022-01-17 10:19:43
回复(0)
方法一：暴力枚举（本题测试用例可通过）
def solution(p, h): i = 1 # 进食速度k while 1: count = 0 i += 1 for j in range(len(p)): if p[j] % i != 0: count = count + p[j]//i+1 else: count = count + p[j]//i if count <= h: return i if __name__ =='__main__': p = list(map(int, input().strip().split())) h = int(input().strip()) print(solution(p, h))# 方法二：利用二分查找优化
def solution2(p, k): count = 0 for j in range(len(p)): if p[j] % k != 0: count = count + p[j] // k + 1 else: count = count + p[j] // k return count if __name__ =='__main__': p = list(map(int, input().strip().split())) h = int(input().strip()) l, r = sum(p)//h, max(p) while l < r: mid = l + (r - l) // 2 count = solution2(p, mid) if count > h: l = mid+1 else: r = mid print(l)
发表于 2020-06-22 10:32:27
回复(0)
20行简单二分。
def check(k, p, h): s = 0 for x in p: s += (x-1)//k +1 return s <= h def bs(l:int, r:int, p, h): res = -1 while l<=r: m = (l+r) // 2 if check(m, p, h): res = m r = m-1 else: l = m+1 return res p = list(map(int,input().split())) h = int(input()) print(bs(1,100000000,p,h))
编辑于 2020-05-16 22:31:45
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int num;
vector<int> p;
while (cin >> num)
{
p.push_back(num);
if (getchar() == '\n')
break;
}
int H;
double K;
cin >> H;
sort(p.begin(), p.end());
if (H < p.size())
return 0;
if (H == p.size())
{
K = p[p.size() - 1];
cout << (int)K;
return 0;
}
double sum = 0.0;
for (int i = 0; i < p.size(); i++)
sum += p[i];
K = ceil(sum / H);
while (K)
{
sum = 0.0;
for (int i = 0; i < p.size(); i++)
{
if (p[i] <= K)
sum += 1;
else
sum += ceil(p[i] / K);
}
if (sum <= H)
{
cout << (int)K;
return 0;
}
K++;
}
}
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int num;
vector<int> p;
while (cin >> num)
{
p.push_back(num);
if (getchar() == '\n')
break;
}
int H;
double K;
cin >> H;
sort(p.begin(), p.end());
if (H < p.size())
return 0;
if (H == p.size())
{
K = p[p.size() - 1];
cout << (int)K;
return 0;
}
double sum = 0.0;
for (int i = 0; i < p.size(); i++)
sum += p[i];
K = ceil(sum / H);
while (K)
{
sum = 0.0;
for (int i = 0; i < p.size(); i++)
{
if (p[i] <= K)
sum += 1;
else
sum += ceil(p[i] / K);
}
if (sum <= H)
{
cout << (int)K;
return 0;
}
K++;
}
}
发表于 2020-02-07 15:04:33
回复(0)
#include <bits/stdc++.h>
using namespace std;
inline int solve(vector<int> &arr,int k){
int h=0;
for(int i=0;i<arr.size();i++){
h+=(arr[i]+k-1)/k;
}
return h;
}
int binary(vector<int> &arr,int start,int end,int aim){
int left=start,right=end;
while(left<=right){
int mid=left+(right-left)/2;
int h=solve(arr,mid);
if(h<=aim){
if(solve(arr,mid-1)>aim)
return mid;
right=mid-1;
}
else
left=mid+1;
}
return left;
}
int main(){
int h,mink,maxk,sum=0;
vector<int> arr;
while(1){
int t;
cin>>t;
arr.push_back(t);
sum+=t;
maxk=max(maxk,t);//最大进食速度
if(cin.get()=='\n')
break;
}
cin>>h;
mink=sum/h; //最小进食速度
cout<<binary(arr,mink,maxk,h);
return 0;
}
发表于 2019-10-17 17:06:27
回复(0)
#include <bits/stdc++.h>
using namespace std;
void read(vector<int> &v){
int num = 0;
char c;
while((c = getchar()) != '\n'){
if(c != ' '){
num = 10 * num + c - '0';
} else {
v.push_back(num);
num = 0;
}
}
v.push_back(num);
}
int main(){
vector<int> p;
int H;
read(p);
scanf("%d", &H);
int l = 0, r = 0, total = 0, res;
for (int i : p){
r += i;
}
res = r;
while(l <= r){
int mid = (l + r) >> 1;
total = 0;
for (int i : p){
total += (i + mid - 1) / mid;
}
if(total <= H){
res = min(res, mid);
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << res << "\n";
return 0;
}
发表于 2019-09-12 08:54:10
回复(0)
一个效率不一定高但思路非常简单的做法
#include<iostream>
#include<vector>using namespace std;
int main()
{
int x;
vector<int>a;
while(cin>>x)
{
a.push_back(x);
if(cin.get()=='\n')break;
}
int h;
cin>>h;
int k;
int len=a.size();
for(k=1;;k++)
{
int sum=0;
for(int j=0;j<len;j++)
{
int t=a[j]/k;
if(a[j]%k)t++;
sum+=t;
}
if(sum<=h)break;
}
cout<<k<<endl;
return 0;
}
发表于 2019-08-22 17:24:16
回复(0)
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
ArrayList<Integer> food=new ArrayList<>();
while(in.hasNextInt()){
food.add(in.nextInt());
}
int num=food.size()-1;
Integer[] fo=food.toArray(new Integer[food.size()]);
int planTime=fo[fo.length-1];
in.close();
int realTime=planTime+1;
int speed;
for(speed=1;realTime>planTime;speed++){
realTime=0;
for(int i=0;i<num;i++){
if((fo[i]%speed)!=0&&fo[i]>speed){
realTime+=fo[i]/speed+1;
}
else if(fo[i]<speed)
realTime++;
else
realTime+=fo[i]/speed;
}
}
System.out.println(--speed);
}
}
发表于 2019-03-02 02:47:39
回复(9)
招商银行信用卡中心2019秋招IT笔试(AI、开发、测试开发方向)第一批
发表于 2018-11-19 12:49:42
回复(0)
"""
暴力尝试，K从1到最大值
"""
import sys
import math
if __name__ == "__main__":
# sys.stdin = open("input.txt", "r")
p = list(map(int, input().strip().split()))
H = int(input().strip())
for K in range(1, max(p) + 1):
temp = 0
for a in p:
temp += math.ceil(a / K)
if temp <= H:
break
print(K)
发表于 2019-07-10 16:42:43
回复(1)
贪心 + 二分查找
理论最小进食速度： 所有喵粮求和 / 给定的小时数
理论最大进食速度：最大堆的喵粮数
在这两个之间二分查找最小实际可行进食速度即可
注：这是一个lower_bound的二分问题，即求最左边满足条件的值 需要相应修改二分查找代码
#include <bits/stdc++.h>
using namespace std;
vector<int> arr;
int H, tmp, sum = 0, mmax = 0, res, mmin;
bool solve(int x, int H) {
int res = 0;
for(int i = 0; i < arr.size(); i++) {
res += (arr[i] % x == 0) ? arr[i] / x: arr[i] / x + 1;
}
return res <= H;
}
int main() {
string line; getline(cin, line);
istringstream iss(line);
while(iss >> tmp) {
arr.push_back(tmp);
mmax = max(mmax, tmp);
sum += tmp;
}
scanf("\n%d", &H);
mmin = (sum % H == 0) ? sum / H: sum / H + 1;
while(mmin < mmax) {
res = (mmin + mmax) / 2;
if(solve(res, H)) mmax = res;//满足条件时 将右边届设为中间值
else mmin = res + 1;
if(solve(mmin, H)) break;//左边界满足时 终止
}
cout<<mmin<<endl;//结果为左边界
}
/*
3 6 7 11
8
*/
编辑于 2019-10-05 17:38:55
回复(0)
二分查找加快速度
import java.util.Scanner;
import static java.lang.System.in;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(in);
String[] str = sc.nextLine().split(" ");
int h = Integer.parseInt(sc.nextLine());
int[] data = new int[str.length];
int maxSpeed = Integer.MIN_VALUE;
for (int i = 0; i < str.length; i++) {
data[i] = Integer.parseInt(str[i]);
maxSpeed = Math.max(maxSpeed, data[i]);
}
int mid = 0;
int minSpeed = 1;
while (minSpeed <= maxSpeed) {
mid = minSpeed + ((maxSpeed - minSpeed) >> 1);
if (getHour(data, mid) <= h) {
maxSpeed = mid - 1;
} else {
minSpeed = mid + 1;
}
}
System.out.println(minSpeed);
}
public static int getHour(int[] data, int k) {
int sum = 0;
for (int i = 0; i < data.length; i++) {
sum += data[i] % k == 0 ? data[i] / k : data[i] / k + 1;
}
return sum;
}
}
编辑于 2019-08-28 17:19:22
回复(1)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Solution3_爱吃猫粮的小招喵 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] line1 = bf.readLine().split(" ");
int n = line1.length;
int h = Integer.parseInt(bf.readLine());
int[] nums = new int[n];
int total = 0;
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(line1[i]);
total += nums[i];
}
int k = total / h;//总的猫粮总量除以时间，至少每小时吃的猫粮数量
while (costTime(nums, k) > h) {
k++;
}
System.out.println(k);
}
private static int costTime(int[] nums, int k) {
int total_h = 0;//吃完猫粮花费的时间
for (int i = 0; i < nums.length; i++) {
total_h += (nums[i] + k - 1) / k; //向上取整，eg: k = 4,nums[i]=5,则需要两个小时
}
return total_h;
}
}
发表于 2019-08-09 20:35:08
回复(5)
我就没见过会慢慢吃的四脚兽🙂
#include <iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
//#include<
using namespace std;
int main()
{
vector<int> nums;
int num;
while(cin>>num)
{
nums.push_back(num);
if(cin.get() == '\n')
break;
}
int hour;
cin>>hour;
int speed = 1;
while(1)
{
int need_time = 0;
for(int i = 0;i<nums.size();i++)
{
if(nums[i] % speed == 0)
need_time += nums[i]/speed;
else {
need_time += nums[i]/speed + 1;
}
}
if(need_time <= hour)
{
cout<<speed<<endl;
break;
}else {
speed++;
}
}
return 0;
}
发表于 2019-08-23 17:39:13
回复(0)
// 二分查找！// 理论最小进食速度： 所有喵粮求和 / 给定的小时数// 理论最大进食速度：最大堆的喵粮数// 在这两个之间二分查找最小实际可行进食速度即可// 注：这是一个lower_bound的二分问题，即求最左边满足条件的值 需要相应修改二分查找代码#include <bits/stdc++.h> using namespace std; vector<int> arr; int H, tmp, sum = 0, mmax = 0, res, mmin; bool solve(int x, int H) { int res = 0; for(int i = 0; i < arr.size(); i++) { res += (arr[i] % x == 0) ? arr[i] / x: arr[i] / x + 1; } return res <= H; } int main() { string line; getline(cin, line); istringstream iss(line); while(iss >> tmp) { arr.push_back(tmp); mmax = max(mmax, tmp); sum += tmp; } scanf("\n%d", &H); mmin = (sum % H == 0) ? sum / H: sum / H + 1; while(mmin < mmax) { res = (mmin + mmax) / 2; if(solve(res, H)) mmax = res;//满足条件时 将右边届设为中间值 else mmin = res + 1; if(solve(mmin, H)) break;//左边界满足时 终止 } cout<<mmin<<endl;//结果为左边界 }
发表于 2023-04-27 19:44:25
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String in = sc.nextLine();
int n = sc.nextInt();
String[] s = in.split(" ");
int[] array = new int[s.length];
for (int i = 0; i < s.length; i++) {
array[i] = Integer.parseInt(s[i]);
}
sc.close();
for (int i = 1; i < Integer.MAX_VALUE; i++) {
int sum = 0;
for (int j = 0; j < array.length; j++) {
if (sum > n) {
break;
}
sum += array[j] / i;
if (array[j] % i != 0) {
sum++;
}
}
if (sum <= n) {
System.out.println(i);
break;
}
}
}
}
发表于 2022-09-03 14:19:24
回复(0)
import sys in_list = [int(i) for i in sys.stdin.readline().strip().split()] num = int(sys.stdin.readline().strip()) left = sum(in_list)//num right = max(in_list) for i in range(left,right+1): res = 0 for j in in_list: if j%i == 0: res+=(j//i) else: res+=(j//i)+1 if res<=num: print(i) break
发表于 2020-06-17 16:01:43
回复(0)
python35，21行搞定。
listx = list(map(int,input().split()))
H=int(input())
def speedz(listx,H,K=1):
while K > 0:
lista=listx[:]
hh=0
for i in range(0,len(listx)):
while lista[i] > 0:
if lista[i]<=K:
hh+=1
lista[i]=0
if lista[i]>K:
lista[i]-=K
hh+=1
if hh>H:
K+=1
continue
else:
print(K)
break
speedz(listx,H)
H=int(input())
def speedz(listx,H,K=1):
while K > 0:
lista=listx[:]
hh=0
for i in range(0,len(listx)):
while lista[i] > 0:
if lista[i]<=K:
hh+=1
lista[i]=0
if lista[i]>K:
lista[i]-=K
hh+=1
if hh>H:
K+=1
continue
else:
print(K)
break
speedz(listx,H)
发表于 2020-06-03 22:15:44
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-02 11:25:30 -
2022-10-28 02:50:37
-
2022-10-22 21:07:37 -
2022-10-21 16:23:10
-
2022-10-08 12:57:14
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
