今天华为机试题,记录一下

1 猴哥蟠桃问题

有n棵蟠桃叔,每颗书上有若干个桃子,然后H小时后会有过来抓人
假设每个小时猴哥吃K个桃子但是每个小时只能吃同一棵树的桃子,例如K为3不能1棵树吃1棵,另一棵树吃两颗,这三颗只能在一棵树吃
然后求K的最小值
输入是一行以空格分隔的n个数字,前n-1个数是每棵树上的蟠桃数,最后一个是H
这题简单,穷举遍历就行了,稍微有个小技巧,就是先将蟠桃数求和然后整除H,出k的最小值,然后再遍历
这个小技巧的含义就是一共32个蟠桃,8小时候来人,你每小时吃的桃子数量小于4时肯定吃不完

2 多处理器并行处理任务问题

说有m个cpu, n个job, 然后每个job有固定用时t1, t2, ... tn,并且每个job独立占用一个cpu,然后调度策略是最小用时job优先,就是短job优先,长job靠后
然后问经过多长时间所有job完成

这题也简单,先把job按用时排个序,然后为每个cpu维护一个队列,存储每个cpu的已经用时
然后遍历每个job(从用时小的开始),再找出已经用时最小的cpu,把这个值加上再存储回去,并重新排一下序
等遍历完所有的job,所有cpu用时中的最大值就是答案

稍微有点优化空间就是可以不用列表存储cpu用时,可以用最小堆存,能减少每次排序cpu用时的损耗,但是感觉那玩意写起来太麻烦