首页 > 试题广场 >

外卖小哥的保温箱

[编程题]外卖小哥的保温箱

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

众所周知，美团外卖的口号是:”美团外卖,送啥都快”。身着黄色工作服的骑手作为外卖业务中商家和客户的重要纽带，在工作中，以快速送餐突出业务能力；工作之余，他们会通过玩智力游戏消遣闲暇时光，以反应速度彰显智慧，每位骑手拿出装有货物的保温箱，参赛选手需在最短的时间内用最少的保温箱将货物装好。

我们把问题简单描述一下:

1 每个货物占用空间都一模一样

2 外卖小哥保温箱的最大容量是不一样的,每个保温箱由两个值描述: 保温箱的最大容量 bi ,当前已有货物个数 ai ,(ai<=bi)

3 货物转移的时候,不必一次性全部转移,每转移一件货物需要花费 1秒的时间

输入描述:

第一行包含n个正整数(1<=n<=100)表示保温箱的数量
第二行有n个正整数a1,a2,…,an(1<=ai<=100)
ai表示第i个保温箱的已有货物个数
第三行有n个正整数b1,b2,…,bn(1<=bi<=100),bi表示第i个保温箱的最大容量
显然,每一个ai<=bi

输出描述:

输出为两个整数k和t, k表示能容纳所有货物的保温箱的最少个数,t表示将所有货物转移到这k个保温箱所花费的最少时间,单位为秒.

示例1

输入

4 
3 3 4 3
4 7 6 5

输出

2 6

说明

我们可以把第一个保温箱中的货物全部挪到第二个保温箱中,花费时间为3秒,此时第二个保温箱剩余容量为1,然后把第四个保温箱中的货物转移一份到第二个保温箱中,转移最后两份到第三个保温箱中.总花费时间也是3秒,所以最少保温箱个数是2,最少花费时间为6秒

示例2

输入

2 
1 1
100 100

输出

1 1

示例3

输入

5 
10 30 5 6 24
10 41 7 8 24

输出

3 11

算法知识视频讲解

菜鸡N+1号

发表于 2020-03-11 12:26:33

这道题整了一晚上，最后看大佬@Albert7 代码思考人生，才想出来怎么做，现在分享一下菜鸡思路博客链接https://blog.csdn.net/qq_28597451/article/details/104691882昨天在牛客网上做笔试题，碰到了一道题动态规划做了一晚上都没做出来，最后看着别人展开全文

DL3D

发表于 2021-10-07 13:01:20

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; int sum_goods = 0; int sum 展开全文

Yuha

发表于 2020-05-05 21:21:50

这道题的总体思路：因为要求最少的保温箱，移动最少的次数。首先按照保温箱的容量进行排序，排序完后就可以求的最少的保温箱个数。但是后面不能直接把后面的保温箱直接移动到容量大的保温箱，因为虽然是最少保温箱个数，但是有可能有多种组合，举个例子 4 3 2 2 2 2 上面的如果要求货物总量为10个，那么后面展开全文