首页 > 试题广场 > 爱吃喵粮的小招喵
[编程题]爱吃喵粮的小招喵

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

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

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

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


输入描述:
第一行输入为喵粮数组,以空格分隔的N个整数

第二行输入为H小时数


输出描述:
最小速度K
示例1

输入

3 6 7 11
8

输出

4
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 回复(2)

二分查找加快速度

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 回复(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;//结果为左边界
}
/*
3 6 7 11
8
*/


编辑于 2019-10-05 17:38:55 回复(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<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)
一个效率不一定高但思路非常简单的做法
#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、开发、测试开发方向)第一批

https://blog.csdn.net/FlushHip/article/details/84137906

发表于 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)
num = list(map(int, input().split()))
h = int(input())
cnt = 0
i = 1
while i <= sum(num):
    for n in num:
        cnt += n//i
        if n%i != 0:
            cnt += 1
    if cnt > h:
        i += 1
        cnt = 0
    else:
        print(i)
        break

发表于 2019-09-18 23:16:10 回复(0)
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)
import java.util.*;
//42
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] arr = sc.nextLine().split(" ");
		Arrays.sort(arr,new Compare());
		int hour = sc.nextInt();
		int k = Integer.parseInt(arr[arr.length-1]);
		int h = 0;
		while (true) {
            for (int i = 0; i < arr.length; i++) {
				if (Integer.parseInt(arr[i]) <= k) {
					h++;
				} else if (Integer.parseInt(arr[i]) / k == Integer.parseInt(arr[i]) * 1.0 / k) {
					h += Integer.parseInt(arr[i]) / k;
				} else {
					h += Integer.parseInt(arr[i]) / k + 1;
				}
			}

			if (h > hour) {
				break;
			}
			k--;
			h = 0;
		}
		System.out.println(k+1);

	}
	static class Compare implements Comparator<String>{ 
                public int compare(String o1, String o2) {
                       return Integer.parseInt(o1)-Integer.parseInt(o2);
		}
		
	}
}

编辑于 2019-09-14 11:22:08 回复(0)
先找到一个原问题的下界,然后从下界出发,找到可行解即输出,如果能找到一个足够好的上界,二分法效率就更快
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)
import sys
paras = []
for i in sys.stdin:
    paras.append([int(i) for i in i.split()])

def func(paras):
    H = paras[1][0]
    food = paras[0]
    time = 0
    if sum(food) % H == 0:
        aveK = int(sum(food) / H)
    else:
        aveK = int(sum(food) / H) + 1
    while True:
        for i in food:
            if i % aveK == 0:
                time += i / aveK
            else:
                time += int(i / aveK) + 1
        if time <= H:
            return aveK
        else:
            aveK += 1
            time = 0
print(func(paras))

发表于 2019-09-13 17:54:13 回复(0)
二分查找即可,这道题的用例又少又小,初始给high设的50都行。。
#include<iostream>
#include<vector>
using namespace std;
 
bool isPossible(vector<int>& piles, int H, int K)//能否在H小时内,以速度K,吃完
{
    int time = 0;
    for (auto p : piles)
    {
        if (K >= p)
            time++;
        if (K < p)
            time += p / K + 1;
    }
    return time <= H;
}
 
int fun(vector<int>& piles, int H)
{
    int low = 1, high = 50;
    while (low < high)
    {
        int mid = (low + high) / 2;
        if (isPossible(piles, H, mid))
            high = mid;
        else
            low = mid + 1;
    }
    return high;
}
 
int main()
{
    int p, H;
    vector<int>piles;
    while (cin >> p)
    {
        piles.push_back(p);
        if (cin.get() == '\n')
            break;
    }
    cin >> H;
    cout << fun(piles, H) << endl;
    return 0;
}


发表于 2019-09-03 16:25:27 回复(0)
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)
from math import ceil
def min_k(food, hours):

    def cal_hours(k):
        count = 0
        for n in food:
            count += ceil(n/k)
        return count

    left = 1
    right = max(food)
    min_k = right
    while left <= right:
        mid = (right + left) // 2
        if cal_hours(mid) <= hours:
            min_k = mid
            right = mid - 1
        else:
            left = mid + 1

    return min_k

food = [int(x) for x in input().split()]
hours = int(input())
print(min_k(food, hours))
发表于 2019-08-24 09:22:09 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> p;
    int a;
    while(cin >> a){
        p.push_back(a);
        if(cin.get() == '\n') break;
    }
    int h;
    cin >> h;
    int k = 1;
    int len = p.size();
    while(k){
        int n = 0;
        for(int i = 0; i < len; i++){
            if(p[i] % k == 0)
                n += p[i]/k;
            else n += p[i]/k + 1;
        }
        if(n <= h) break;
        else ++k;
    }
    cout << k << endl;
}

发表于 2019-08-21 20:07:04 回复(0)
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
   vector<int> num;
    int h,n;
    int len;
    int count;
 while(cin>>n)
 {
        num.push_back(n);
 
        if(cin.get() == '\n') break;    
 }
    cin>>h;
    len = int(num.size());
    for(int k=1;;k++)   // 速度从1开始往上加,一直加到符合条件的最小速度
    {
       count=0;
       for(int i=0;i<len;i++)
        {
           
            if(num[i]%k==0)          
                  count+=num[i]/k;
            else                           //如果剩下的不足一个小时 也要花一个小时
                  count+=(num[i]/k+1);
           if(count>h)break;
        } 
        if(count<=h)
        {
            cout<<k;
            break;
        }
    }
}
发表于 2019-08-16 17:39:40 回复(0)
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    vector<int> v;
    int x, H, sum = 0, max = 0;
    int low, high, hour = 0;
    while(cin>>x){
        v.push_back(x);
        sum += x;
        max = max > x ? max : x;
        if(cin.get() == '\n')
            break;
    }
    cin>>H;
    if(H == v.size()){
        cout<<max<<endl;
        return 0;
    }
    //两边+1,-1扩大搜索范围
    low = sum/H-1;
    high = sum/(H-v.size())+1;
    for(int i = low; i <= high; ++i){
        hour = 0;
        for(int j = 0; j < v.size(); ++j){
            hour += v[j] / i;
            if(v[j] % i)
                ++hour;
        }
        if(hour <= H){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}
H至少要大于等于猫粮堆数,等于时最小速度为猫粮中最大的容量
大于时最小速度low为sum/H-1,最大速度high为sum/(H-N)+1,-1/+1扩大范围,然后在low和high之间使用二分法查找,这里使用从最小的速度开始循环遍历
发表于 2019-08-15 17:41:49 回复(0)