首页 > 试题广场 > 爱吃喵粮的小招喵
[编程题]爱吃喵粮的小招喵
  • 热度指数:8419 时间限制: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

输出

4

二分查找加快速度

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)
贪心  + 二分查找
理论最小进食速度: 所有喵粮求和 / 给定的小时数
理论最大进食速度:最大堆的喵粮数
在这两个之间二分查找最小实际可行进食速度即可
注:这是一个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.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 回复(4)
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++;
    }
}
发表于 2020-02-07 15:04:33 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int x,h;
    vector<int> p;
    while(cin>>x)
        p.push_back(x);
    int n = p.size()-1;
    h = p[n];
    int k = 1, t;
    do{
        t = 0;
        for(int i=0;i<n;i++)
            t += ceil(1.0*p[i]/k);
        k++;
    }while(t>h);
    cout<<k-1<<endl;
    return 0;
}

发表于 2019-12-06 01:05:58 回复(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<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)

运行时间:3ms

占用内存:492k

#include<bits/stdc++.h>
using namespace std;
int main(){
int a;
    vector<int> m;
    while(cin >> a) {
    m.push_back(a);
    if (getchar() == '\n')
         break;
    }
    int h;         
    cin>>h;
    sort(m.begin(),m.end());
    reverse(m.begin(),m.end());
//cout<<m[0]<<'\n';
    int k=m[0],mh=m.size();
    while(mh<=h){
        k--;mh=0;
        for(int i=0;i<m.size();i++){
            int k1=k,count=1;
            while(m[i]>k1){
                k1=k1+k;
                count++;
            }
            mh=mh+count;
        //    cout<<mh<<'\n'   ;
        }        
    }
    cout<<k+1<<endl;


}



发表于 2020-04-28 09:52:34 回复(0)
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

int main(int argc, char* argv[]){
    string line;
    int H, val, largest = 0;
    getline(cin, line);
    cin >> H;
    stringstream ss(line);
    vector<int> food;
    while(ss >> val) {
        if(val > largest) largest = val;
        food.push_back(val);
    }
    
    int low = 1, high = largest;
    while(low < high){
        int K = low + (high - low)/2;
        int hour = 0;
        for(int idx = 0; idx < food.size(); idx++){
            hour += (food[idx] + K-1) / K;
        }
        if(hour > H) low = K+1;
        else high = K;
    }
    cout << low << endl;
    return 0;
}

编辑于 2020-04-11 11:50:42 回复(0)
import java.util.Arrays;
import java.util.Scanner;

/**
 * 招行卡中心: 爱吃喵粮的小招喵
 */
public class Main {

    private static int MAX_FOOD = Integer.MIN_VALUE;
    private static int HOUR = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] s = sc.nextLine().split(" ");
        int[] foods = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            foods[i] = Integer.parseInt(s[i]);
            MAX_FOOD = Math.max(MAX_FOOD, foods[i]);
        }
        HOUR = Integer.parseInt(sc.nextLine().trim());
        Arrays.sort(foods);
        System.out.println(bFind(foods));

    }

    private static int bFind(int[] foods) {
        int l = 1, r = MAX_FOOD;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (canEatUp(foods, m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    private static boolean canEatUp(int[] foods, int speed) {
        int time = 0;
        for (int i = foods.length - 1; i >= 0; i--) {
            time += ((foods[i] / speed) + (foods[i] % speed == 0 ? 0 : 1));
            if (time > HOUR) {
                return false;
            }
        }
        return true;
    }
}

发表于 2020-04-08 00:46:34 回复(0)
#include <iostream>
(720)#include <vector>
#include<algorithm>
using namespace std;
 
int main()
{
    // 小招喵喜欢吃喵粮。这里有 N 堆喵粮,第 i 堆中有 p[i] 粒喵粮。喵主人离开了,将在 H 小时后回来。
    // 小招喵可以决定她吃喵粮的速度 K (单位:粒/小时)。每个小时,她将会选择一堆喵粮,从中吃掉 K 粒。如果这堆喵粮少于 K 粒,她将吃掉这堆的所有喵粮,然后这一小时内不会再吃更多的喵粮。
    // 小招喵喜欢慢慢吃,但仍然想在喵主人回来前吃掉所有的喵粮。
    // 返回她可以在 H 小时内吃掉所有喵粮的最小速度 K(K 为整数)。
    //3 6 7 11
    //8
    //4
    int a = 0;
    vector<int> nums;
    while (cin >> a)
    {
        nums.push_back(a);
    }
    int h = nums[nums.size() - 1];
    nums.pop_back();
    sort(nums.begin(),nums.end());
    //每堆的平均次数27/8->3.
    int sum=0;
    for(int i=0;i<nums.size();i++){
        sum=sum+nums[i];
    }
    int m=sum/h;
    int count=0;
    vector<int> temp=nums;
    int flag=0;
    for(int i=m;i<=nums[nums.size()-1];i++){
        count=0;
        temp=nums;
        for(int j=0;j<nums.size();j++){
            if(temp[j]<=i){
                //吃一个小时
                count++;
            }else{
                temp[j]=temp[j]-i;
                j--;
                count++;
            }
        }
        if(count<=h){
            flag=i;
            break;
        }
         
    }
    cout<<flag<<endl;
    return 0;
}

发表于 2020-04-07 16:59:12 回复(0)
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)
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[] s = sc.nextLine().split(" ");
        int H=sc.nextInt();
        int[] arr=new int[s.length];
        int max=0;
        for(int i=0;i<s.length;i++){
            arr[i]=Integer.parseInt(s[i]);
            max=Math.max(max,arr[i]);
        }
        int min=Integer.MAX_VALUE;
        int last=0;
        for(int i=1;i<=max;i++){
            int count=0;
            for(int j=0;j<s.length;j++){
                count+=Math.ceil(1.0*arr[j]/i);
            }
            if(count==H){
                System.out.println(i);
                return;
            }
            
            //特殊情况,没有能恰好达到H小时吃完的时候,寻找最优的K
            if(Math.abs(H-count)<min){
                min=Math.abs(H-count);
                last=i;
            }
        }
        System.out.println(last);
    }
}
发表于 2020-03-19 22:47:12 回复(0)
C++,输入处理较麻烦,从minK到maxK的遍历还可以用二分查找加速
#include <iostream>
(720)#include <vector>
#include <string>
(765)#include <sstream>
#include <algorithm>
(831)#include <numeric>
#include <cmath>
 
using namespace std;
 
int calcK(vector<int>& p, int H)
{
    int minK = ceil(accumulate(p.begin(), p.end(), 0) / static_cast<double>(H));
    int maxK = *max_element(p.begin(), p.end());
    for (int k = minK; k <= maxK; ++k) {
        int cnt = 0;
        for (int i : p) {
            while (i > 0) {
                i -= k;
                ++cnt;
                if (cnt > H)
                    break;
            }
        }
        if (cnt <= H)
            return k;
    }
    return maxK;
}
 
int main()
{
    string str;
    vector<string> strs;
    while (getline(cin, str, '\n'))
        strs.push_back(str);
    stringstream ss(strs[0]);
    vector<int> p;
    while (getline(ss, str, ' '))
        p.push_back(stoi(str));
    int H = stoi(strs[1]);
    cout << calcK(p, H) << endl;
    return 0;
}


发表于 2020-03-13 12:17:00 回复(0)