我要招人

去企业版

首页 > 试题广场 >

爱吃喵粮的小招喵

[编程题]爱吃喵粮的小招喵

热度指数：9741 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小招喵喜欢吃喵粮。这里有 N 堆喵粮，第 i 堆中有 p[i] 粒喵粮。喵主人离开了，将在 H 小时后回来。

小招喵可以决定她吃喵粮的速度 K （单位：粒/小时）。每个小时，她将会选择一堆喵粮，从中吃掉 K 粒。如果这堆喵粮少于 K 粒，她将吃掉这堆的所有喵粮，然后这一小时内不会再吃更多的喵粮。

小招喵喜欢慢慢吃，但仍然想在喵主人回来前吃掉所有的喵粮。

返回她可以在 H 小时内吃掉所有喵粮的最小速度 K（K 为整数）。

输入描述:

第一行输入为喵粮数组，以空格分隔的N个整数

第二行输入为H小时数

输出描述:

最小速度K

示例1

输入

3 6 7 11
8

输出

算法知识视频讲解

Python

Jancydc

方法一：暴力枚举（本题测试用例可通过）

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)

Python

faka

from math import ceil

nums = list(map(int, input().split()))
H = int(input())

def eatAll(K:int) -> bool:
    return sum(ceil(n / K) for n in nums) <= H


l, r = 1, 10000000
while l <= r:
    mid = int((l+r)/2)
    if eatAll(mid) and (not eatAll(mid - 1)):
        print(mid)
        break
    elif eatAll(mid):
        r = mid - 1
    elif not eatAll(mid):
        l = mid + 1

二分查找

发表于 2019-10-19 11:26:16 回复(0)

Python

我要扛offer回家

import sys
p=list(map(int,sys.stdin.readline().split()))
h=int(sys.stdin.readline().strip())
for i in range(1,max(p)+1):
    hour=0
    for j in p:
        if j<i:
            hour+=1
        elif j%i==0:
            hour+=j//i
        else:
            hour=hour+j//i+1
    if hour<=h:
        print(i)
        break

编辑于 2019-09-14 15:54:19 回复(0)

Python

牛客835408486号

先找到一个原问题的下界，然后从下界出发，找到可行解即输出，如果能找到一个足够好的上界，二分法效率就更快

import math
p = list(map(int, input().strip().split()))
h = int(input().strip())

lb = math.ceil(sum(p) / h)  # 最小速度的下界

while True:
    if sum(math.ceil(i/lb) for i in p) <= h:  # 满足则直接输出
        print(lb)
        break
    else:  # 否则提高速度
        lb += 1

编辑于 2019-09-14 10:56:49 回复(0)

Python

贾志统

def func(food_array, h):
    k = 1
    while True:
        s = 0
        for food in food_array:
            s += food // k
            if food % k > 0:
                s += 1
        if s > h:
            k += 1
        else:
            break
    print(k)


while True:
    try:
        food_array = list(map(int, input().split()))
        h = int(input())
        func(food_array, h)
    except:
        break

发表于 2019-08-26 17:13:33 回复(0)

Python

欧巴禾

arr = [int(elem) for elem in input().split()]
H = int(input())
speed = 1 while True:
    Now = 0; Next = 0  for number in arr: if number<=speed:
            Now+=1  elif number%speed==0:
            Now+=number//speed else:
            Now+=number//speed+1  if number<=(speed+1):
            Next+=1  elif number%(speed+1)==0:
            Next+=number//(speed+1) else:
            Next+=number//(speed+1)+1  if Now>H and Next<=H: print(speed+1) break  else:
        speed+=1

发表于 2019-08-13 15:18:19 回复(0)

Python

ElonB

"""
暴力尝试，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)