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

小招喵喜欢吃喵粮。这里有 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 回复(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-18 15:42:24 回复(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)
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))
发表于 今天 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)
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)

#二分大法好

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
vector<int> input;
int H;
int temp_int;
bool Can_finish(int K,int H ,vector<int >input )
{
    int temp_time=0;
    for (int i = 0;i != input.size();i++)
    {
        temp_time += input[i] / K + (input[i] % K != 0);
    }
    if (H >= temp_time)
        return true;
    else
        return false;
}

int main()
{
    while (cin >> temp_int)
    {
        input.push_back(temp_int);
    }
    H = input[input.size() - 1];
    input.erase(input.end() - 1);
    vector<int> temp_vec=input;
    sort(temp_vec.begin(), temp_vec.end());
    reverse(temp_vec.begin(), temp_vec.end());//只是懒得找最大一堆猫粮是多少,就偷个懒,排序结果
    int MAX = temp_vec[0];
    int MIN = 1;
    while (MAX-MIN>=2)
    {
        int MID =(MAX + MIN)/2;
        if (Can_finish(MID, H, input))
        {
            MAX=MID;
        }
        else
        {
            MIN= MID+1;
        }
    }
    if (Can_finish(MIN, H, input))
        cout << MIN;
    else 
        cout << MAX;
        return 0;
}
发表于 2019-08-13 12:02:40 回复(1)

这种题就是想考分页算法吧。。。

题目没给数据量,直接暴力竟然过了。。。

hhhha,其实可以使用二分优化一下的。。。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().trim().split("\\s+");
        if("".equals(strs[0])) return;
        int n = strs.length;
        int[] arr = new int[n];
        for(int i = 0; i < n; i ++) {
            arr[i] = Integer.valueOf(strs[i]);
        }

        int H = sc.nextInt();
        if(H < n) return;
        int K = 1;
        while(true) {
            int m = 0;
            for(int i = 0; i < n; i ++) {
                m += (arr[i] + K - 1) / K;
            }

            if(m <= H) break;
            K ++;
        }

        System.out.println(K);
    }
}
发表于 2019-08-12 00:26:37 回复(0)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int value;
	int h;
	vector<int>arr;
	while (cin >> value)
	{
		arr.push_back(value);
		if (getchar() == '\n')
			break;
	}
	cin >> h;
	sort(arr.begin(), arr.end());
	int kmin = 1;
	int max = arr[arr.size() - 1];
	if (h < arr.size())
		return -1;
	while (kmin < max)
	{
		int res = 0;
		for (int i = 0; i < arr.size(); i++)
		{
			if (arr[i] % kmin == 0)
				res += arr[i] / kmin;
			else
				res += arr[i] / kmin + 1;
		}
		if (res <= h)
			break;
		else
			kmin++;
	}
	cout << kmin << endl;
	system("pause");
	return 0;
}

发表于 2019-08-06 16:41:33 回复(0)
//也是暴力求解的思路,但是不是从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)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int>v;
    int temp;
    int sum = 0;
    while(cin>>temp)
    {
        v.push_back(temp);
        sum+=temp;
    }
    // 取得小时数
    int hour = v.back();
    v.pop_back();
    int time;
    // 最低速度起始的数值
    int speed = (sum-hour)/hour;
    while(1)
    {
        time = 0;
        for(int i=0;i<v.size();i++)
        {
            time+=v[i]/speed;
            // 如果一堆最后余下一点 则仍可以撑一个小时
            if(v[i]%speed)
                time+=1;
        }
        // 若以当前速度吃不完 则速度加一
        if(time>hour)
            speed++;
        else break;
    }
    cout<<speed<<endl;
    return 0;
}

发表于 2019-07-30 09:03:35 回复(0)
/*
本来当时想的是更高效的方法的,但是实际还是暴力法更好写出来。
直接从1到最大的值,用speed 表示当前的速度,用result 表示用当前速度吃要多长时间
result 的计算方法是 对于每一堆猫粮,都是 如果小于speed ,直接吃完 则result++
如果刚好分几次吃完,则result+=Catfood.get(j)/speed
如果还剩些 ,则result+=Catfood.get(j)/speed+1;
这样子转换表达,和一轮计算一次的方法还是有些差别的,更好表示一些。
*/
//package test1; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.Scanner;     public class Main     {         static public void main ( String []args)         {             food();         }     static void food()     {         Scanner in = new Scanner(System.in);         String inArray= in.nextLine();         String []InNumber=inArray.split(" ");         ArrayList<Integer> Catfood=new ArrayList<>();                  for(int i=0;i<InNumber.length;i++ )         {             Catfood.add(Integer.parseInt(InNumber[i]));          }         int hour=in.nextInt();         Collections.sort(Catfood);          int speed=1;         for(;speed<=Catfood.get(Catfood.size()-1);speed++)         {             int result=0;             for(int j=0;j<Catfood.size();j++)             {                 if(Catfood.get(j)<speed)                     result++;                 else if(Catfood.get(j)%speed==0) result+=Catfood.get(j)/speed;                 else if(Catfood.get(j)%speed!=0) result+=Catfood.get(j)/speed+1;             }             if (result>hour) continue;             else                  {                     System.out.println(speed);                     break;                 }         }     }     }
发表于 2019-07-29 10:49:19 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int>catsnack;
    int snack,totaltime;
    int count;
    while(cin>>snack)
    {
        catsnack.push_back(snack);
        if(cin.get()=='\n')
        {
            break;
        }
    }
    cin>>totaltime;
    int spendtime=0;
   //暴力求解,满足花费时间不大于总时间,即跳出循环
    for(int k=1;;k++)
    {
        
        for(int i=0;i<catsnack.size();i++)
        {
            spendtime+=(catsnack[i]/k);
            if((catsnack[i]%k)!=0)
            {
                spendtime++;
            }
        }
        if(spendtime<=totaltime)
        {
            count=k;
            break;
        }
        else
        {
            spendtime=0;
        }
    }
    cout<<count<<endl;
    return 0;
}

发表于 2019-07-26 18:36:21 回复(0)
先求一小时能吃最多堆粒的速度即为最快速度,然后以该速度为初始值,逐次减1,每次求出该速度吃喵粮的总时间,若总时间大于H小时,则退出循环。此时的速度即为最小速度。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static int H;
    public static void main(String[] args) throws IOException{
        BufferedReader buffer=new BufferedReader(new InputStreamReader(System.in));
        String[] str_p=buffer.readLine().split(" ");
        int[] p=new int[str_p.length];
        for(int i=0;i<str_p.length;i++){
            p[i]=Integer.parseInt(str_p[i]);
        }
        H=Integer.parseInt(buffer.readLine());
        
        int maxFood=p[0];
        for(int i=0;i<p.length;i++){
            if(maxFood<p[i]){
                maxFood=p[i];
            }
        }
        
        int maxSpeed=maxFood;
        
        int totalTime=0;
        int K=maxSpeed;
        for(;K>=1;K--){
            totalTime=0;
            for(int j=0;j<p.length;j++){
                totalTime+=computeMax(p[j],K);
            }
            if(totalTime>H){
                break;
            }
        }
        System.out.println(K+1);
    }
    private static int computeMax(int num,int den){
        int result=0;
        if(num%den==0){
            result=num/den;
        }else{
            result=num/den+1;
        }
        return result;
    }
}

发表于 2019-07-20 17:16:10 回复(0)