爱吃喵粮的小招喵

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

热度指数：9829 时间限制：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

输出

算法知识视频讲解

Java

pein531

在[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)

Java

天台爱情

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int len = s.length;
        int[] nums = new int[len];
        for(int i = 0;i < len;i++){
            nums[i] = Integer.parseInt(s[i]);
        }
        int k;
        int h = sc.nextInt();
        int cnt =  h + 1;
        for(k = 1;;k++){
            cnt = 0;
            for(int j = 0;j < len;j++){
                if((nums[j]%k) == 0 ){
                    cnt += (nums[j]/k);
                }
                else{
                    cnt += (nums[j]/k+1);
                }
            }
            if(cnt <= h){
                break;
            }
        }
        System.out.println(k);
    }
}

我的挺简单的吧

发表于 2020-03-26 23:58:29 回复(0)

Java

JLU小浪

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)

Java

顾欣全网最可爱

//也是暴力求解的思路，但是不是从1开始，而是从总的猫粮数除以总时间，即最理想情况下的最慢速度。

import java.util.*;

public class Main {
public static int count=0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s=in.nextLine();
int h=in.nextInt();
String []help=s.split(" ");
int p[]=new int[help.length];
int sum=0;
for(int i=0;i<p.length;i++)
{
p[i]=Integer.parseInt(help[i]);
sum=sum+p[i];
}
System.out.println(eat(h,p,sum));
}
public static int eat(int h,int []p,int sum){

int res;
if(sum%h==0)
{
res=sum/h-1;
}else{
res=sum/h;
}
int time=Integer.MAX_VALUE;
while(time>h){
res++;
time=0;
for(int i=0;i<p.length;i++)
{
if(p[i]%res==0){
time=time+p[i]/res;
}else{
time=time+p[i]/res+1;
}
}

}
return res;
}
}

发表于 2019-08-01 00:44:19 回复(0)

Java

pursueJ

实在是想不出什么好办法了，只会用暴力法了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int[] p = new int[s.length];
        int sum = 0;
        for(int i = 0;i < p.length;i++){
            p[i] = Integer.parseInt(s[i]);
            sum += p[i];
        }

        String ss = br.readLine();
        int h = Integer.parseInt(ss);

        int k = sum % h == 0 ? sum / h : sum / h + 1;

        while(true){
            int result = 0;
            for(int i = 0;i < p.length;i++){
                result += p[i] % k ==0 ? p[i] / k : p[i] / k + 1;
            }
            if(result > h){
                k++;
            }else{
                break;
            }
        }
        System.out.println(k);
    }
    
}

发表于 2019-07-17 17:19:43 回复(0)