不按照时间先后了,反正都是在一个晚上。
先是顺丰,若干选择,两道编程题。编程题:1.服务器管理(分配);2.赏金猎人。
一道贪心,一道动规。题目本身不难,据后了解好多同学做题时都是走错了路。我只做了第一道,还没AC……
1. 服务器管理
题目描述
小A有一批服务器要出租,每一个服务器有一个固定的带宽;客户根据自己需要的带宽租用服务器,一台服务器只能租给一个人。
小A现有n个服务器,第 i 台服务器对应的带宽为a_i;现有m个客户需要服务器,第 i 位客户需要的带宽为b_i,预算为c_i(注意:这里 i 的含义不同)。现在求小A的服务器最多能租多少钱?
要求:服务器带宽独立不可叠加,不能成功租出则输出0。输入输出规则和用例如下。
1 | Input: |
解题思路
因为服务器带宽独立不可叠加,所以优先选择可以满足带宽需求的资金最充裕的客户。采用贪心算法求解,使用带宽最小的服务器来尝试满足客户需求,所以要先进行排序。